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

2021-09-01 HGNULB 约 5 分钟

文章信息 6 个分类 · 3 个标签

分类

LeetCode CodeTop 中等 未解决 1-2 旷视

标签

数组 矩阵 模拟

题目描述

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

题意分析

在固定的八乘八棋盘上，有一个国王和若干皇后，返回当前局面下能够直接攻击国王的皇后坐标，输出顺序不限。皇后沿横线、竖线和对角线攻击，途中不能越过其他棋子。

因此，共行、共列或处于同一条对角线只是方向条件，还必须没有更近的皇后遮挡。同一个从国王出发的方向上，最多只有最近的一枚皇后能够直接攻击国王。

解法：八方向扫描

核心思路

[!blue]

与其从每个皇后出发再判断它到国王之间是否被挡住，可以反过来站在国王位置，沿八条攻击方向向外寻找第一枚皇后。它与国王之间的格子已经逐一确认为空，因此一定能直接攻击；在它后面的皇后都被它挡住，不再检查这个方向即可。

先用固定大小的布尔棋盘 occupied 标记皇后位置，查询某格是否存在皇后只需常量时间。行增量 dr 和列增量 dc 各取负一、零、一，排除二者同时为零，正好得到四个直线方向和四个对角方向。

每个方向从国王的相邻格开始，坐标每次加上同一个方向增量。如果越界，说明这条方向上没有更多棋子；如果遇到皇后，就记录坐标并结束当前方向。其他方向仍然独立继续寻找。

能攻击国王的皇后必然位于这八条射线之一，且必须是所在方向最近的皇后，所以扫描不会漏掉目标。反过来，每条射线找到的首枚皇后与国王之间没有遮挡，加入的每个坐标也都符合要求。

解题步骤

1. 创建八乘八的布尔表，将所有皇后坐标标记为真。
2. 枚举行列增量的八个非零组合。
3. 从该方向的相邻格开始逐格前进，行列都需保持在零到七之间。
4. 遇到第一枚皇后时记录坐标并停止当前射线；否则一直扫描到棋盘外。
5. 所有方向处理完后返回坐标列表。

代码实现

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+1)$，其中 q 为皇后数。标记输入后，八条射线各最多检查七个格子，扫描部分是固定开销。
• 空间复杂度：$O(1)$，布尔棋盘大小固定，结果最多只有八个位置。

关键点总结

[!green]

• 从国王向外寻找首枚皇后，把方向和遮挡两个条件一次解决。
• 每条射线最多贡献一个结果，命中后只结束这一方向。
• 排除零方向，保证坐标不断变化并最终命中或越界。

易错点总结

[!yellow]

• 命中后仍继续记录更远皇后，会把被遮挡的棋子也误算成可攻击。
• 只判断是否共行、共列或共对角线，不能排除同方向上的遮挡关系。
• 保留 (0, 0) 方向会使坐标不前进，扫描可能永远无法结束。
• 只检查坐标上界，向左或向上扫描时仍可能用负下标访问棋盘。
• 找到一枚就返回整个结果，会漏掉其他独立方向上的可攻击皇后。

相似题目

题目	难度	关联与区别
999. 可以被一步捕获的棋子数	简单	同样沿方向寻找第一个可见棋子，车只有四个方向，皇后包含四条对角线。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2021/82536159

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