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.
Solution:
class Solution {
int[] dx = new int[]{-1, -1, -1, 0, 0, 1, 1, 1};
int[] dy = new int[]{-1, 0, 1, -1, 1, -1, 0, 1};
public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
List<List<Integer>> result = new ArrayList();
boolean[][] visited = new boolean[8][8];
Set<List<Integer>> qSet = new HashSet();
Set<Integer> attacked = new HashSet();
for (int[] q : queens) {
qSet.add(Arrays.asList(q[0], q[1]));
}
Deque<List<Integer>> queue = new ArrayDeque();
queue.offer(Arrays.asList(king[0], king[1]));
visited[king[0]][king[1]] = true;
while (!queue.isEmpty()) {
List<Integer> curr = queue.poll();
int x = curr.get(0), y = curr.get(1);
if (qSet.contains(curr)) {
int dir = canAttack(new int[]{x, y}, king);
if (dir != -1 && attacked.add(dir)) {
result.add(curr);
}
}
for (int i = 0; i < 8; i ++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < 8 && ny >= 0 && ny < 8 && !visited[nx][ny]) {
visited[nx][ny] = true;
queue.offer(Arrays.asList(nx, ny));
}
}
}
return result;
}
private int canAttack(int[] queen, int[] king) {
int qx = queen[0], qy = queen[1];
int kx = king[0], ky = king[1];
if (qx == kx) {
if (qy > ky) return 0;
else return 1;
}
if (qy == ky) {
if (qx > kx) return 2;
else return 3;
}
if (Math.abs(qx - kx) == Math.abs(qy - ky)) {
if (qx > kx) {
if (qy > ky) {
return 4;
} else {
return 5;
}
} else {
if (qy > ky) {
return 6;
} else {
return 7;
}
}
}
return -1;
}
}