LeetCode 1222. 可以攻击国王的皇后
目录
题目描述
题意分析
要的是所有「能攻击到国王」的皇后坐标，顺序任意。皇后的攻击范围是八个方向上的直线，但攻击会被挡住——一条射线上如果站了多枚皇后，只有离国王最近的那一枚能攻击到，后面的被前面的挡住了。
这个「遮挡」规则是本题的全部内容。忽略它就变成了「找出所有与国王同行、同列、同对角线的皇后」，那是完全不同的答案。
棋盘固定为 8×8，坐标范围 $[0, 7]$；皇后互不重叠，也不会和国王重合。棋盘尺寸是常量而不是变量，这是个很强的信号：任何以棋盘大小为规模的枚举都是常数级代价，不需要为此优化。
换个角度：既然每个方向上只有最近的那一枚有效，答案的规模天然被限制在 8 以内，与皇后总数无关。
边界：某个方向上一枚皇后都没有、国王站在角落导致多个方向立刻出界、同一射线上连续排布多枚皇后。
解法：八方向扫描
核心思路
皇后只能沿横、竖、两条对角线攻击。与其逐个皇后判断共线后再处理遮挡，不如从国王向八个方向发出射线：每条射线上遇到的第一枚皇后可以攻击国王，更远的皇后都会被它挡住。
棋盘固定为 8×8，可先用布尔数组记录皇后位置，使每格查询为
O(1)。八个方向可由行、列增量各取-1、0、1并排除(0,0)得到，避免漏写方向。扫描某个方向时维护不变量：当前位置之前、国王之后的所有格子都已确认没有皇后。因此当前位置若有皇后，它就是该方向最近且唯一可见的皇后；记录后立即停止该方向。
正确性说明：任一能攻击国王的皇后必位于八条射线之一。算法逐格检查每条射线，不会漏掉最近皇后；找到第一枚后停止，恰好排除所有被遮挡的更远皇后。因此返回集合与所有可攻击国王的皇后完全一致。
解题步骤
- 将每枚皇后的坐标标记到
occupied[8][8]。- 枚举行增量
dr和列增量dc；跳过二者都为 0 的组合。- 从国王的相邻格
(kingRow + dr, kingCol + dc)开始，沿当前方向逐格前进。- 若越界，此方向没有可见皇后；若命中皇后，记录坐标并立即结束此方向。
- 扫描完八个方向后返回结果，顺序可任意。
例如国王在
[0,0]，同一行有皇后[0,1]、[0,4]，只有[0,1]会被记录；竖直方向的[1,0]会挡住[4,0]。国王在边角、某方向没有皇后或八个方向都有皇后，都由相同边界循环处理。
代码实现
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
boolean[][] occupied = new boolean[8][8];
for (int[] queen : queens) {
occupied[queen[0]][queen[1]] = true;
}
List<List<Integer>> answer = new ArrayList<>();
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
if (dr == 0 && dc == 0) {
continue;
}
int row = king[0] + dr;
int col = king[1] + dc;
while (row >= 0 && row < 8 && col >= 0 && col < 8) {
if (occupied[row][col]) {
List<Integer> position = new ArrayList<>(2);
position.add(row);
position.add(col);
answer.add(position);
break;
}
row += dr;
col += dc;
}
}
}
return answer;
}
}
func queensAttacktheKing(queens [][]int, king []int) [][]int {
var occupied [8][8]bool
for _, queen := range queens {
occupied[queen[0]][queen[1]] = true
}
answer := make([][]int, 0, 8)
for dr := -1; dr <= 1; dr++ {
for dc := -1; dc <= 1; dc++ {
if dr == 0 && dc == 0 {
continue
}
row, col := king[0]+dr, king[1]+dc
for row >= 0 && row < 8 && col >= 0 && col < 8 {
if occupied[row][col] {
answer = append(answer, []int{row, col})
break
}
row += dr
col += dc
}
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(q)$。标记 q 枚皇后需要线性时间；八条射线各至多检查 7 格，是固定常数。
- 空间复杂度：$O(1)$。8×8 占用表和最多 8 个方向均为固定大小；返回结果不计入额外空间。
关键点总结
- 从国王向外扫描后，“遮挡”自然变成命中后的
break，无需另做区间检查。- 每个方向只需要最近的皇后；同一射线上不可能有第二个有效答案。
- 固定棋盘直接使用布尔占用表，比坐标字符串或线性查找更简单可靠。
- 行、列增量都从
{-1, 0, 1}中选择并排除(0, 0)，恰好得到八个方向。
易错点总结
- 命中后继续扫描：皇后
[0,1]会挡住[0,4]；两者都加入结果就违反遮挡规则。- 只判断皇后与国王是否同行、同列或同对角线：仍会把同一射线上被挡住的皇后算进去。
- 把
(0,0)当成方向：坐标永远不变，若国王格没有皇后，循环会无限执行。- 从国王位置而非相邻格开始且忘记先移动：会重复检查原地，甚至配合
(0,0)形成死循环。- 边界只检查上限：国王在
[0,0]向左上走时坐标变为负数，必须同时检查row >= 0与col >= 0。- 命中后结束整个搜索：每个方向最多取一枚，但八个方向彼此独立；只能结束当前方向。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 999. 可以被一步捕获的棋子数 | 简单 | 只有四个正交方向，且遇到己方棋子要停下不计数 |
| 51. N 皇后 | 困难 | 反过来构造无冲突布局，用回溯加对角线占用标记 |
| 289. 生命游戏 | 中等 | 八邻域只看一圈不延伸，难点在原地更新的状态编码 |
| 149. 直线上最多的点数 | 困难 | 方向不再是八个而是任意斜率，需要用最简分数做键 |