1222. Queens That Can Attack the King

QUESTION:

On an 8x8 chessboard, there can be multiple Black Queens and one White King.

Given an array of integer coordinates queens that represents the positions of the Black Queens, and a pair of coordinates king that represent the position of the White King, return the coordinates of all the queens (in any order) that can attack the King.

Example 1:

Input: queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0] Output: [[0,1],[1,0],[3,3]] Explanation:
The queen at [0,1] can attack the king cause they’re in the same row. The queen at [1,0] can attack the king cause they’re in the same column. The queen at [3,3] can attack the king cause they’re in the same diagnal. The queen at [0,4] can’t attack the king cause it’s blocked by the queen at [0,1]. The queen at [4,0] can’t attack the king cause it’s blocked by the queen at [1,0]. The queen at [2,4] can’t attack the king cause it’s not in the same row/column/diagnal as the king. Example 2:

Input: queens = [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]], king = [3,3] Output: [[2,2],[3,4],[4,4]] Example 3:

Input: queens = [[5,6],[7,7],[2,1],[0,7],[1,6],[5,1],[3,7],[0,3],[4,0],[1,2],[6,3],[5,0],[0,4],[2,2],[1,1],[6,4],[5,4],[0,0],[2,6],[4,5],[5,2],[1,4],[7,5],[2,3],[0,5],[4,2],[1,0],[2,7],[0,1],[4,6],[6,1],[0,6],[4,3],[1,7]], king = [3,4] Output: [[2,3],[1,4],[1,6],[3,7],[4,3],[5,4],[4,5]]

Constraints:

1 <= queens.length <= 63 queens[0].length == 2 0 <= queens[i][j] < 8 king.length == 2 0 <= king[0], king[1] < 8 At most one piece is allowed in a cell.

EXPLANATION:

做个题目首先还得了解国际象棋，不过从例子中可以看到，queue可以8个方向进行移动，也就是kill，但是queue不能跨越其他单位进行kill。那么我们就可以反向来思考，将king进行8个方向的移动，如果碰到了queue，就说明是可以被kill的，同时，遇到了之后就停止继续那个方向。既然我们需要在棋盘上进行移动，就需要首先将棋盘摆出来。
思路：

  1. 定义一个二维数组用来表示棋盘
  2. 将queue摆放在棋盘上，也就是将棋盘上queue的位置标注为1
  3. 定义8个方向，dx和dy表示每个方向上x，y的delta值
  4. 在每个方向上对king在棋盘范围内进行移动，如果遇到了queue（plant格子==1），那么将该格子放入到结果中，同时终止该方向上的移动
  5. 8个方向都移动结束后返回结果

    SOLUTION:

    class Solution {
 public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
     ArrayList<List<Integer>> result = new ArrayList<>();
     int[][] plant = new int[8][8];
     for(int i = 0;i<queens.length;i++){
         plant[queens[i][0]][queens[i][1]] = 1; // 在棋盘上标注queue的位置
     }
     int[] dy = new int[]{0,0,-1,1,-1,1,-1,1};
     int[] dx = new int[]{-1,1,0,0,-1,-1,1,1};// 定义8个方向上的x，y的delta值
     for(int i = 0;i<dy.length;i++) { // 8个方向进行移动
         int x = king[0]+dx[i];
         int y = king[1]+dy[i];
         while (x>=0 && x<=7 && y>=0 && y<=7){ // 移动也就是一直加上对应的dx和dy
             if(plant[x][y]==1){
                 ArrayList<Integer> tmp = new ArrayList<>();
                 tmp.add(x);
                 tmp.add(y);
                 result.add(tmp);
                 break; // 无法跨越其他棋子进行kill，所以在此处进行break，停止该方向上的搜索
             }
             x+=dx[i];
             y+=dy[i];
         }
     }
     return result;
 }
}
>
--> return <--