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:

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<>();