LeetCode 999. 可以被一步捕获的棋子数
目录
题目描述
题意分析
给一个 8×8 的字符棋盘，
'R'是白车（棋盘上恰好一个），'B'是白象（己方棋子），'p'是黑卒（敌方棋子），'.'是空格。车只能沿上下左右四个方向直线移动，不能穿过任何棋子。问一步之内白车能吃掉多少个黑卒。规则要落实成三条判定。第一，车沿某个方向直线走，第一个遇到的非空格子决定了这个方向的结果：是黑卒就能吃（计 1），是白象就被挡住（计 0），因为不能吃己方棋子也不能越过它。第二，一个方向最多只能吃到 1 个卒——吃掉第一个之后车就停在那里，第二个卒被第一个挡着，一步之内够不着。第三，走到棋盘边界仍未遇到任何棋子，那个方向就是 0。
所以答案的取值范围是 0 到 4，四个方向各自独立贡献 0 或 1。这个「独立」很关键——四个方向互不干扰，可以逐个扫描后相加，不需要任何全局权衡。
棋盘尺寸固定为 8×8，这是最强的约束信号：规模是常数，怎么写都不会超时，所以本题考的完全是规则的准确落实与代码组织，而不是算法。也正因为如此，写得清楚、方向处理不冗余，比写得快更重要。
边界方面：题目保证棋盘上恰好有一个
'R'，不必处理找不到或找到多个的情形（但代码里把初值设成-1并单向覆盖是稳妥的习惯）；扫描时必须严格判断行列是否落在[0, 8)内，越界即停止。
解法：四方向模拟扫描
核心思路
这题没有「暴力 → 优化」的层次，因为棋盘是常数规模，暴力本身就是最优。真正需要设计的是如何把四个方向的重复逻辑写成一份。
如果对上、下、左、右各写一段
while，就会得到四段几乎相同、只有下标增减方向不同的代码。这种写法不仅冗长，而且四份里只要有一份把符号写反或把边界判错，就会出现只在特定用例上暴露的 bug。更好的组织方式是用方向数组：把四个方向的行增量与列增量分别列成dr = {-1, 1, 0, 0}与dc = {0, 0, -1, 1}，然后用一个循环变量d遍历四组，扫描逻辑只写一遍。单个方向的扫描逻辑是一个「射线投射」：从车的相邻格子出发，沿固定方向一格一格前进，遇到三种情况之一就停：
- 越界（行或列跑出
[0, 8)）：该方向无贡献，循环条件自然结束；- 遇到
'B'：被己方棋子挡住，无贡献，break；- 遇到
'p'：吃掉它，计数加一，break。遇到
'.'则继续前进。这三个出口互斥且覆盖了全部情况，所以不会漏判也不会重复计数。维持的不变量是：内层循环每次进入时，
(x, y)都是当前方向上尚未检查过的、离车最近的格子，且车与它之间的所有格子都是空的。正因如此，第一次遇到非空格子时就能立刻下结论并终止——这条不变量同时解释了为什么「一个方向最多吃一个」是自动成立的，不需要额外计数控制。起点必须是
(r + dr[d], c + dc[d])而不是(r, c)。从车自己的格子开始，第一次检查就会读到'R'，既不是'B'也不是'p'，代码会当成空格继续前进——虽然侥幸不出错，但语义混乱；更糟的是如果有人把'R'也纳入判断，逻辑会立刻崩坏。直接从相邻格出发最干净。
解题步骤
- 定位白车：双重循环扫描 8×8 棋盘，找到
'R'并记下(r, c)。为什么必须先找车：所有射线都从它出发，位置未知就无从扫描。为什么初值设-1：便于在调试时发现「没找到」的异常情况，虽然题目保证一定存在。- 准备方向数组：
dr = {-1, 1, 0, 0}、dc = {0, 0, -1, 1}，四组分别代表上、下、左、右。为什么用数组而不是写四段：把「方向」参数化后扫描逻辑只写一遍，四个方向共享同一份边界判断与终止规则，出错面缩小到四分之一。- 外层遍历四个方向：
d从 0 到 3。- 内层从相邻格出发做射线扫描：初始
x = r + dr[d]、y = c + dc[d]。为什么不从车自己开始：车所在格子已知是'R'，检查它没有意义还会混淆语义。- 循环条件是边界检查：
x >= 0 && x < 8 && y >= 0 && y < 8。为什么把边界放在循环条件而不是循环体里：一旦越界就不该再访问board[x][y]，放在条件里能保证访问永远合法；写在体内先访问再判断会直接越界崩溃。- 遇到
'B'立即break：己方棋子既不能吃也不能穿过，该方向到此为止，不计数。- 遇到
'p'计数后break：吃掉第一个卒，车停在那里，后面的格子够不着。为什么必须break而不是continue：不break会把同一方向上更远的卒也算进去，答案偏大。- 否则前进一格：
x += dr[d]、y += dc[d]。这一步只在遇到'.'时执行，对应「继续投射」。- 返回累加结果。
以官方示例的棋盘走一遍：白车在第 3 行第 2 列（0 基），它的上方第 1 行第 2 列有一个
'p'，下方第 6 行第 2 列有一个'p'，左边第 3 行第 1 列有一个'p'，右边第 3 行第 4 列有一个'B'、更远处第 3 行第 6 列还有一个'p'，其余为'.'。
方向 0（上，dr = -1）：从(2, 2)出发是'.'，前进到(1, 2)遇到'p'，计数变 1 并终止。
方向 1（下，dr = +1）：从(4, 2)出发一路是'.'，到(6, 2)遇到'p'，计数变 2 并终止。
方向 2（左，dc = -1）：从(3, 1)出发就是'p'，计数变 3 并终止。
方向 3（右，dc = +1）：从(3, 3)出发是'.'，前进到(3, 4)遇到'B'，被挡住，break，不计数。注意更远处(3, 6)的那个'p'虽然存在，但车过不去，绝不能算——这正是'B'分支存在的意义。
返回 3，与预期一致。再看一个空棋盘的用例：除白车外全是
'.'。四个方向都会一路走到越界，循环条件失败自然退出，计数保持 0，返回 0——边界检查放在循环条件里让这种情况无需任何特判。
代码实现
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)$。凭什么：棋盘尺寸固定为 8×8，定位白车最多 64 次比较，四个方向每个最多前进 7 格，合计不超过 92 次常数操作，与任何输入变量都无关。若把边长记作
L，则为 $O(L^2)$（定位）加 $O(L)$（扫描）。- 空间复杂度：$O(1)$。凭什么：只用了两个长度为 4 的方向数组和几个整型变量，没有复制棋盘也没有开辅助矩阵。
关键点总结
- 四方向、八方向的遍历统一用方向数组参数化，扫描逻辑只写一份。这不只是少打字——四段复制粘贴的代码里，符号写反或边界写漏的概率是单份的四倍。
- 「射线投射」是网格题的基本子过程：从起点沿固定方向前进，遇到第一个非空目标就下结论并终止。识别出这个模式，
break的位置就不会放错。- 边界检查要写在循环条件里而不是循环体内，保证任何一次
board[x][y]的访问都发生在合法范围内；这也让「一路走到边界」的情形无需特判。- 起点从相邻格而非自身开始，能避免把起点自己纳入判定；凡是「从某点向外看」的扫描都该这么起步。
- 阻挡物与目标物必须分成两个独立分支，且都要终止扫描——只是终止后一个计数、一个不计数。把两者合并或漏掉阻挡分支，是这类题最常见的错误。
- 面试视角：这是道纯实现题，面试官看的是代码组织能力。用方向数组而不是四段复制、把边界判断放进循环条件、在遇到
'B'和'p'时都break——把这三点写出来并顺口解释一句，就足以体现工程素养；若被追问扩展，可以说改成象或后（斜向）只需往方向数组里补四组对角增量，扫描逻辑一行都不用改。
易错点总结
- 错误写法：遇到
'p'后不break→ 用例中某方向上有两个卒时，两个都被计数，答案从 3 变成 4，而一步只能吃最近的那一个。- 错误写法：漏掉
'B'的分支，只判'p'→ 用例中车的右侧先有'B'再有'p'，被挡住的卒也被算进去，答案从 3 变成 4。- 错误写法：遇到
'B'时写continue而不是break→continue不会推进x、y，用例中直接陷入死循环。- 错误写法：扫描从车自身
(r, c)开始 → 用例中第一次检查读到'R'，若代码把非'B'非'p'一律当空格则侥幸正确，但一旦加上「遇到任何非空格子就停」的判断，四个方向全部立刻终止，答案恒为 0。- 错误写法：边界检查写在循环体内，先访问
board[x][y]再判断是否越界 → 用例中车位于棋盘边缘时首次访问即越界，Java 抛数组越界异常，Go 直接 panic。- 错误写法：边界写成
x <= 8或y <= 8→ 用例中车在第 7 行时向下扫描会读到board[8][y]，越界崩溃。- 错误写法：方向数组的
dr与dc配对错位，比如写成dr = {-1,1,0,0}、dc = {-1,1,0,0}→ 用例中「上」变成了左上斜向，车的移动规则被改成了象，答案完全错误。- 错误写法：忘记在前进时同时更新
x和y→ 用例中横向扫描时x不变本就正确，但纵向扫描若漏了x += dr[d]，指针原地打转形成死循环。- 错误写法：把找车的循环写成找到后不
break也不记录、或用if (board[i][j] == 'R') return ...提前返回 → 前者若棋盘上出现多个'R'（题目不会给，但防御性写法应稳）会取到最后一个；后者直接跳过了扫描逻辑。- 错误写法：用
board[x][y] != '.'统一判断「遇到棋子」后再区分类型 → 逻辑等价但会把'R'也纳入（若起点写错），且分支嵌套更深；直接对'B'与'p'分别判断更清晰。- 错误写法：认为答案最多是 4 就用四个布尔变量分别记录 → 与直接累加等价但更啰嗦，且容易在最后求和时漏掉某一个方向。
- 错误写法：把黑卒
'p'与白象'B'的角色搞反，遇到'B'计数、遇到'p'停止 → 用例中答案从 3 变成 1，读题时必须确认哪个是敌方棋子。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1222. 可以攻击国王的皇后 | 中等 | 同为射线投射，但方向扩展到八个且要输出坐标，方向数组的价值更明显 |
| 54. 螺旋矩阵 | 中等 | 也用方向数组，但方向按规则轮转且需要边界收缩，比固定四射线复杂一层 |
| 733. 图像渲染 | 简单 | 四方向扩散但要递归/入队并标记访问，考的是连通块而不是直线阻挡 |
| 200. 岛屿数量 | 中等 | 四方向搜索的经典题，重点在访问标记的设置时机 |
| 51. N 皇后 | 困难 | 同为棋盘攻击范围判定，但需要回溯搜索并用对角线编号做 $O(1)$ 冲突检测 |
| 874. 模拟行走机器人 | 中等 | 方向数组配合转向索引，障碍物用哈希集合查询而非直接读网格 |
| 867. 转置矩阵 | 简单 | 纯下标映射，无方向概念，是网格题里最基础的一档 |