---

1222. 可以攻击国王的皇后

• 标签：数组、矩阵、模拟
• 难度：中等

题目链接

• 1222. 可以攻击国王的皇后 - 力扣

题目大意

描述：在一个 $8 \times 8$ 的棋盘上，放着若干个皇后和一个国王。皇后的走法是可以沿上下左右、对角线八个方向任意延伸，但不能越过其他棋子。

要求：返回所有可以直接攻击到国王的皇后的坐标。

说明：

• 棋盘大小为 $8 \times 8$。
• $1 \le queens.length \le 63$。
• $queens[i]$ 和 $king$ 都是长度为 $2$ 的坐标数组，分别表示行和列（$0 \le 值 < 8$）。
• 同一个位置最多放一个棋子。

示例：

• 示例 1：

输入：queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0]
输出：[[0,1],[1,0],[3,3]]
解释：国王在 (0,0)，皇后在 (0,1) 可以向右攻击，(1,0) 可以向下攻击，(3,3) 可以对角线攻击。

解题思路

思路 1：八个方向模拟

1. 核心思想

棋盘只有 $8 \times 8 = 64$ 个格子，非常小。可以直接模拟皇后走法。

从国王的位置出发，向八个方向分别延伸查找。每个方向上遇到的第一个皇后就是能攻击到国王的皇后（因为更远的皇后会被这个皇后挡住）。

2. 具体步骤

第 1 步：将皇后的位置存入集合（用于快速判断某个位置是否有皇后）。

第 2 步：定义八个方向向量：上、下、左、右、左上、右上、左下、右下。

第 3 步：对每个方向，从国王位置开始，沿方向一步步延伸：

• 如果超出棋盘边界，停止。
• 如果该位置有皇后，加入结果列表，停止（被挡住）。
• 否则继续延伸。

第 4 步：返回结果列表。

3. 结合示例走一遍

$queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0]$

从 $(0,0)$ 向八个方向延伸：

• 向右 $(0,+1)$：$(0,1)$ 有皇后 → 结果 $[0,1]$
• 向下 $(+1,0)$：$(1,0)$ 有皇后 → 结果 $[1,0]$
• 向右下 $(+1,+1)$：$(1,1)$ 无 → $(2,2)$ 无 → $(3,3)$ 有皇后 → 结果 $[3,3]$
• 向左 $(-1,0)$：超出边界
• 向上 $(0,-1)$：超出边界
• 向左下 $(+1,-1)$：超出边界
• 向左上 $(-1,-1)$：超出边界
• 向右上 $(-1,+1)$：超出边界

最终结果 $[[0,1],[1,0],[3,3]]$。

思路 1：代码

class Solution:
    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:
        # 将皇后位置存入集合
        queen_set = set(tuple(q) for q in queens)

        # 八个方向
        dirs = [(-1, -1), (-1, 0), (-1, 1),
                (0, -1),           (0, 1),
                (1, -1),  (1, 0),  (1, 1)]

        ans = []
        for dr, dc in dirs:
            r, c = king[0] + dr, king[1] + dc
            while 0 <= r < 8 and 0 <= c < 8:
                if (r, c) in queen_set:
                    ans.append([r, c])
                    break
                r += dr
                c += dc

        return ans

思路 1：复杂度分析

• 时间复杂度：$O(1)$，最大搜索范围是 $8 \times 8$ 棋盘，每个方向最多延伸 $8$ 格，共 $8$ 个方向，所以最多 $64$ 次判断，常数时间。
• 空间复杂度：$O(1)$，存储皇后的集合最多 $63$ 个元素，常数空间。