题目描述 这是 LeetCode 上的 1222. 可以攻击国王的皇后 ,难度为 中等 。
在一个 8x8
的棋盘上,放置着若干「黑皇后」和一个「白国王」。
给定一个由整数坐标组成的数组 queens
,表示黑皇后的位置;以及一对坐标 king
,表示白国王的位置,返回所有可以攻击国王的皇后的坐标(任意顺序)。
示例 1:
输入:queens = , king = 输出: 解释: 的皇后可以攻击到国王,因为他们在同一行上。 的皇后可以攻击到国王,因为他们在同一列上。 的皇后可以攻击到国王,因为他们在同一条对角线上。 的皇后无法攻击到国王,因为她被位于 的皇后挡住了。 的皇后无法攻击到国王,因为她被位于 的皇后挡住了。 的皇后无法攻击到国王,因为她和国王不在同一行/列/对角线上。
示例 2:
示例 3:
提示:
$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 原题链接和其他优选题解。