LeetCode 999. 可以被一步捕获的棋子数

2021-05-27 HGNULB 约 6 分钟

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

分类

LeetCode CodeTop 简单 未解决 1-2 字节

标签

数组 矩阵 模拟

题目描述

✅ 999. 可以被一步捕获的棋子数

题意分析

棋盘固定为 8 × 8，包含唯一白车 R、白象 B、黑卒 p 和空格 .。白车一步可以沿上下左右移动任意格，但不能越过任何棋子，求当前有多少个黑卒可供它一步捕获。

统计的是不同的可捕获目标，不是让白车连续走多步吃掉棋子。因此只需从白车的原位置检查四条直线，不需要移动棋盘上的棋子或继续搜索捕获后的局面。

解法：四方向模拟扫描

核心思路

[!blue]

先遍历棋盘，找到白车坐标 (r, c)。用 dr、dc 的对应元素表示上下左右四种单位移动，每个方向都从 (r + dr[d], c + dc[d]) 开始，跳过车自身。

扫描途中，只要当前位置为空格，就继续沿同一方向前进。第一枚棋子若是白象，白车既不能捕获它，也不能穿过去，该方向结束；若是黑卒，前面的路径全为空，说明能一步到达它，答案加一后同样结束，因为它挡住了更远的棋子。

所以一个方向至多贡献一个目标，且只取决于最先遇到的非空格。四条射线覆盖了白车的所有合法移动方向，它们除车自身外互不相交，将各方向结果相加就不会遗漏或重复计算黑卒。

解题步骤

1. 找到唯一白车的位置。
2. 枚举上下左右四个方向，从相邻格出发。
3. 空格继续，遇到象或卒停止；只有卒增加答案。
4. 返回四个方向的总数。

每次先判断坐标在棋盘内，再读取格子；空格分支必须移动坐标，否则循环不会前进。车位于边缘时，朝外的方向会直接结束。题目保证存在唯一白车，查找结束后其坐标一定有效，答案范围为 0 到 4。

代码实现

class Solution {
    public int numRookCaptures(char[][] board) {
        int r = -1;
        int c = -1;

        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (board[i][j] == 'R') {
                    r = i;
                    c = j;
                }
            }
        }

        // 上、下、左、右四个方向共享同一份扫描逻辑。
        int[] dr = {
            -1,
            1,
            0,
            0
        };
        int[] dc = {
            0,
            0,
            -1,
            1
        };
        int answer = 0;

        for (int d = 0; d < 4; d++) {
            // 从车的相邻格出发，跳过车自身。
            int x = r + dr[d];
            int y = c + dc[d];

            while (x >= 0 && x < 8 && y >= 0 && y < 8) {
                if (board[x][y] == 'B') {
                    // 己方棋子挡路，该方向作废。
                    break;
                }

                if (board[x][y] == 'p') {
                    // 只能吃到最近的那一个。
                    answer++;
                    break;
                }

                x += dr[d];
                y += dc[d];
            }
        }

        return answer;
    }
}

func numRookCaptures(board [][]byte) int {
    r, c := -1, -1
    for i := 0; i < 8; i++ {
        for j := 0; j < 8; j++ {
            if board[i][j] == 'R' {
                r, c = i, j
            }
        }
    }

    // 上、下、左、右四个方向共享同一份扫描逻辑。
    dr := []int{
        -1,
        1,
        0,
        0,
    }
    dc := []int{
        0,
        0,
        -1,
        1,
    }
    answer := 0
    for d := 0; d < 4; d++ {
        // 从车的相邻格出发，跳过车自身。
        x, y := r+dr[d], c+dc[d]
        for x >= 0 && x < 8 && y >= 0 && y < 8 {
            if board[x][y] == 'B' {
                // 己方棋子挡路，该方向作废。
                break
            }
            if board[x][y] == 'p' {
                // 只能吃到最近的那一个。
                answer++
                break
            }
            x += dr[d]
            y += dc[d]
        }
    }
    return answer
}

复杂度分析

• 时间复杂度：棋盘固定八乘八，时间为 $O(1)$。
• 空间复杂度：$O(1)$。

关键点总结

[!green]

• 遇到任何棋子都不能继续穿过。
• 统计可供选择的捕获目标，不是在同一步吃掉多个卒。
• 坐标越界前停止，不能先访问再判断。

易错点总结

[!yellow]

• 遇到卒后继续扫描：把被挡住的更远卒也算进去。
• 忽略白象：会错误地穿过己方棋子。
• 遇到阻挡物只 continue 不移动坐标：循环会停在原地。
• 加入对角线方向：白车只能横向或纵向移动。

相似题目

题目	难度	关联与区别
361. 轰炸敌人	中等	同样沿行列寻找视线可达对象，本题遇第一个棋子即停止，原题在墙分隔段内累计敌人数。
1222. 可以攻击国王的皇后	中等	同样从目标沿方向寻找第一个可见棋子，皇后有八个方向，车只有四个方向。

转载与许可

作者 HGNULB

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

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