LC 1222. 可以攻击国王的皇后

题目描述

这是 LeetCode 上的 1222. 可以攻击国王的皇后 ,难度为 中等

在一个 8x8 的棋盘上,放置着若干「黑皇后」和一个「白国王」。

给定一个由整数坐标组成的数组 queens,表示黑皇后的位置;以及一对坐标 king,表示白国王的位置,返回所有可以攻击国王的皇后的坐标(任意顺序)。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
输入:queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0]

输出:[[0,1],[1,0],[3,3]]

解释:
[0,1] 的皇后可以攻击到国王,因为他们在同一行上。
[1,0] 的皇后可以攻击到国王,因为他们在同一列上。
[3,3] 的皇后可以攻击到国王,因为他们在同一条对角线上。
[0,4] 的皇后无法攻击到国王,因为她被位于 [0,1] 的皇后挡住了。
[4,0] 的皇后无法攻击到国王,因为她被位于 [1,0] 的皇后挡住了。
[2,4] 的皇后无法攻击到国王,因为她和国王不在同一行/列/对角线上。

示例 2:

1
2
3
输入:queens = [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]], king = [3,3]

输出:[[2,2],[3,4],[4,4]]

示例 3:

1
2
3
输入: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]

输出:[[2,3],[1,4],[1,6],[3,7],[4,3],[5,4],[4,5]]

提示:

  • $1 <= queens.length <= 63$
  • $queens[i].length = 2$
  • $0 <= queens[i][j] < 8$
  • $king.length = 2$
  • $0 <= king[0], king[1] < 8$
  • 一个棋盘格上最多只能放置一枚棋子。

模拟

创建一个二维数组 dirs 来表示八个方向的坐标偏移,同时使用变量 step 来表示从国王位置出发的步数。

在每个方向 i 上,通过 step 步可以到达的坐标为 $(x + dirs[i][0] \times step, y + dirs[i][1] \times step)$。

模拟过程中,我们可使用布尔数组 checked 来记录已处理的方向,当我们遇到皇后或越过棋盘时,可标记该方向已处理。

Java 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
int[][] dirs = new int[][]{{1,0},{0,1},{0,-1},{-1,0},{1,1},{-1,-1},{1,-1},{-1,1}};
public List<List<Integer>> queensAttacktheKing(int[][] qs, int[] k) {
boolean[][] vis = new boolean[10][10];
for (int[] q : qs) vis[q[0]][q[1]] = true;
int x = k[0], y = k[1], step = 1;
List<List<Integer>> ans = new ArrayList<>();
boolean[] checked = new boolean[8];
while (step <= 8) {
for (int i = 0; i < 8; i++) {
if (checked[i]) continue;
int nx = x + dirs[i][0] * step, ny = y + dirs[i][1] * step;
if (nx < 0 || nx >= 8 || ny < 0 || ny >= 8) {
checked[i] = true;
} else {
if (!vis[nx][ny]) continue;
List<Integer> list = new ArrayList<>();
list.add(nx); list.add(ny);
ans.add(list);
checked[i] = true;
}
}
step++;
}
return ans;
}
}

C++ 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {
vector<vector<int>> dirs {{1,0},{0,1},{0,-1},{-1,0},{1,1},{-1,-1},{1,-1},{-1,1}};
vector<vector<int>> ans;
vector<vector<bool>> vis(8, vector<bool>(8, false));
for (auto& queen : queens) vis[queen[0]][queen[1]] = true;
int x = king[0], y = king[1], step = 1;
vector<bool> checked(8, false);
while (step <= 8) {
for (int i = 0; i < 8; i++) {
if (checked[i]) continue;
int nx = x + step * dirs[i][0];
int ny = y + step * dirs[i][1];
if (nx < 0 || nx >= 8 || ny < 0 || ny >= 8) {
checked[i] = true;
} else {
if (!vis[nx][ny]) continue;
ans.push_back({nx, ny});
checked[i] = true;
}
}
step++;
}
return ans;
}
};

Python 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:
dirs = [[1,0],[0,1],[0,-1],[-1,0],[1,1],[-1,-1],[1,-1],[-1,1]]
vis = [[False] * 8 for _ in range(8)]
for q in queens:
vis[q[0]][q[1]] = True
x, y = king
ans = []
checked = [False] * 8
step = 1
while step <= 8:
for i in range(8):
if checked[i]: continue
nx, ny = x + dirs[i][0] * step, y + dirs[i][1] * step
if nx < 0 or nx >= 8 or ny < 0 or ny >= 8:
checked[i] = True
else:
if not vis[nx][ny]: continue
ans.append([nx, ny])
checked[i] = True
step += 1
return ans

TypeScript 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function queensAttacktheKing(queens: number[][], king: number[]): number[][] {
let dirs = [[1,0],[0,1],[0,-1],[-1,0],[1,1],[-1,-1],[1,-1],[-1,1]];
let vis: boolean[][] = Array.from({length:8},()=>Array(8).fill(false));
for (let q of queens) vis[q[0]][q[1]] = true;
let x = king[0], y = king[1], step = 1;
let ans: number[][] = [];
let checked: boolean[] = Array(8).fill(false);
while (step <= 8) {
for (let i = 0; i < 8; i++) {
if (checked[i]) continue;
let nx = x + dirs[i][0] * step, ny = y + dirs[i][1] * step;
if (nx < 0 || nx >= 8 || ny < 0 || ny >= 8) {
checked[i] = true;
} else {
if (!vis[nx][ny]) continue;
ans.push([nx, ny]);
checked[i] = true;
}
}
step++;
}
return ans;
};

  • 时间复杂度:$O(C)$,其中 $C = 8 \times 8$ 为棋盘总大小
  • 空间复杂度:$O(C)$,其中 $C = 8 \times 8$ 为棋盘总大小

BFS

上述模拟过程也可以使用 BFS 方式进行。

相比于直接模拟,BFS 无须使用额外变量记录处理过的方向以及当前位置与国王的距离。

Java 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
int[][] dirs = new int[][]{{1,0},{0,1},{0,-1},{-1,0},{1,1},{-1,-1},{1,-1},{-1,1}};
public List<List<Integer>> queensAttacktheKing(int[][] qs, int[] k) {
boolean[][] vis = new boolean[10][10];
for (int[] q : qs) vis[q[0]][q[1]] = true;
Deque<int[]> d = new ArrayDeque<>();
for (int i = 0; i < 8; i++) {
int x = k[0] + dirs[i][0], y = k[1] + dirs[i][1];
if (x < 0 || x >= 8 || y < 0 || y >= 8) continue;
d.addLast(new int[]{x, y, i});
}
List<List<Integer>> ans = new ArrayList<>();
while (!d.isEmpty()) {
int[] info = d.pollFirst();
int x = info[0], y = info[1], p = info[2];
if (vis[x][y]) {
List<Integer> list = new ArrayList<>();
list.add(x); list.add(y);
ans.add(list);
} else {
int nx = x + dirs[p][0], ny = y + dirs[p][1];
if (nx < 0 || nx >= 8 || ny < 0 || ny >= 8) continue;
d.addLast(new int[]{nx, ny, p});
}
}
return ans;
}
}

C++ 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {
vector<vector<int>> dirs = {{1,0},{0,1},{0,-1},{-1,0},{1,1},{-1,-1},{1,-1},{-1,1}};
vector<vector<bool>> vis(8, vector<bool>(8, false));
for (vector<int>& queen : queens) vis[queen[0]][queen[1]] = true;
deque<vector<int>> d;
for (int i = 0; i < 8; i++) {
int x = king[0] + dirs[i][0], y = king[1] + dirs[i][1];
if (x < 0 || x >= 8 || y < 0 || y >= 8) continue;
d.push_back({x, y, i});
}
vector<vector<int>> res;
while (!d.empty()) {
vector<int> cur = d.front();
d.pop_front();
if (vis[cur[0]][cur[1]]) {
res.push_back({cur[0], cur[1]});
} else {
int nx = cur[0] + dirs[cur[2]][0], ny = cur[1] + dirs[cur[2]][1];
if (nx < 0 || nx >= 8 || ny < 0 || ny >= 8) continue;
d.push_back({nx, ny, cur[2]});
}
}
return res;
}
};

Python 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def queensAttacktheKing(self, queens, king):
dirs = [[1,0],[0,1],[0,-1],[-1,0],[1,1],[-1,-1],[1,-1],[-1,1]]
vis = [[False]*8 for _ in range(8)]
for q in queens: vis[q[0]][q[1]] = True
d = deque()
for i in range(8):
x = king[0] + dirs[i][0]
y = king[1] + dirs[i][1]
if x < 0 or x >= 8 or y < 0 or y >= 8: continue
d.append([x, y, i])
ans = []
while d:
cur = d.popleft()
if vis[cur[0]][cur[1]]:
ans.append([cur[0], cur[1]])
else:
x = cur[0] + dirs[cur[2]][0]
y = cur[1] + dirs[cur[2]][1]
if x < 0 or x >= 8 or y < 0 or y >= 8: continue
d.append([x, y, cur[2]])
return ans

TypeScript 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function queensAttacktheKing(queens: number[][], king: number[]): number[][] {
let dirs = [[1,0],[0,1],[0,-1],[-1,0],[1,1],[-1,-1],[1,-1],[-1,1]];
let vis: boolean[][] = Array(8).fill(false).map(() => Array(8).fill(false));
queens.forEach(q => vis[q[0]][q[1]] = true);
let d: number[][] = [];
for (let i = 0; i < 8; i++) {
let x = king[0] + dirs[i][0], y = king[1] + dirs[i][1];
if (x < 0 || x >= 8 || y < 0 || y >= 8) continue;
d.push([x, y, i]);
}
let res = [];
while (d.length !== 0) {
let cur = d.shift();
if (vis[cur[0]][cur[1]]) {
res.push([cur[0], cur[1]]);
} else {
let x = cur[0] + dirs[cur[2]][0], y = cur[1] + dirs[cur[2]][1];
if (x < 0 || x >= 8 || y < 0 || y >= 8) continue;
d.push([x, y, cur[2]]);
}
}
return res;
};

  • 时间复杂度:$O(C)$,其中 $C = 4 \times 8$ 为四条线的总步数
  • 空间复杂度:$O(C)$,其中 $C = 8 \times 8$ 为棋盘总大小

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1222 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!