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

题目描述

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

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

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

示例 1：

输入：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：

输入：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：

输入：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 代码：

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;
                    add(ans, nx, ny);
                    checked[i] = true;
                }
            }
            step++;
        }
        return ans;
    }
    void add(List<List<Integer>> ans, int x, int y) {
        List<Integer> list = new ArrayList<>();
        list.add(x); list.add(y);
        ans.add(list);
    }
}

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

---

BFS

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

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

Java 代码：

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;
    }
}

• 时间复杂度：$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 原题链接和其他优选题解。