LeetCode 题解工作台
可以被一步捕获的棋子数
给定一个 8 x 8 的棋盘， 只有一个 白色的车，用字符 'R' 表示。棋盘上还可能存在白色的象 'B' 以及黑色的卒 'p' 。空方块用字符 '.' 表示。 车可以按水平或竖直方向（上，下，左，右）移动任意个方格直到它遇到另一个棋子或棋盘的边界。如果它能够在一次移动中移动到棋子的方格，则能够 吃…
3
题型
6
代码语言
3
相关题
当前训练重点
简单 · 数组·matrix
答案摘要
我们先遍历棋盘，找到车的位置 $(i, j)$，然后从 $(i, j)$ 出发，向上下左右四个方向遍历： - 如果不是边界且不是象，则继续向前走；
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·matrix 题型思路
题目描述
给定一个 8 x 8 的棋盘，只有一个 白色的车，用字符 'R' 表示。棋盘上还可能存在白色的象 'B' 以及黑色的卒 'p'。空方块用字符 '.' 表示。
车可以按水平或竖直方向（上，下，左，右）移动任意个方格直到它遇到另一个棋子或棋盘的边界。如果它能够在一次移动中移动到棋子的方格，则能够 吃掉 棋子。
注意：车不能穿过其它棋子，比如象和卒。这意味着如果有其它棋子挡住了路径，车就不能够吃掉棋子。
返回白车 攻击 范围内 兵的数量。
示例 1：
输入：[[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]] 输出：3 解释： 在本例中，车能够吃掉所有的卒。
示例 2：
输入：[[".",".",".",".",".",".",".","."],[".","p","p","p","p","p",".","."],[".","p","p","B","p","p",".","."],[".","p","B","R","B","p",".","."],[".","p","p","B","p","p",".","."],[".","p","p","p","p","p",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]] 输出：0 解释： 象阻止了车吃掉任何卒。
示例 3：
输入：[[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","p",".",".",".","."],["p","p",".","R",".","p","B","."],[".",".",".",".",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."]] 输出：3 解释： 车可以吃掉位置 b5，d6 和 f5 的卒。
提示：
board.length == 8board[i].length == 8board[i][j]可以是'R'，'.'，'B'或'p'- 只有一个格子上存在
board[i][j] == 'R'
解题思路
方法一：模拟
我们先遍历棋盘，找到车的位置 ，然后从 出发，向上下左右四个方向遍历：
- 如果不是边界且不是象，则继续向前走；
- 如果是卒，则答案加一，并停止该方向的遍历。
遍历完四个方向后，即可得到答案。
时间复杂度 ，其中 和 分别是棋盘的行数和列数，本题中 。空间复杂度 。
class Solution:
def numRookCaptures(self, board: List[List[str]]) -> int:
dirs = (-1, 0, 1, 0, -1)
n = len(board)
for i in range(n):
for j in range(n):
if board[i][j] == "R":
ans = 0
for a, b in pairwise(dirs):
x, y = i + a, j + b
while 0 <= x < n and 0 <= y < n and board[x][y] != "B":
if board[x][y] == "p":
ans += 1
break
x, y = x + a, y + b
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Tests candidate's ability to simulate piece movements in a grid-based problem.
- question_mark
Evaluates problem-solving with matrix traversal and handling of obstacles.
- question_mark
Checks for clarity in handling edge cases like pieces blocking the path.
常见陷阱
外企场景- error
Not accounting for bishops blocking the rook's path, leading to incorrect captures.
- error
Failing to stop when encountering a boundary or obstacle, allowing false positives for captures.
- error
Overcomplicating the solution by not taking advantage of the fixed 8x8 grid size.
进阶变体
外企场景- arrow_right_alt
Modify the problem to include multiple rooks and calculate all possible captures.
- arrow_right_alt
Implement the solution on larger boards (e.g., 10x10) and handle boundary conditions.
- arrow_right_alt
Change the problem to count the number of squares the rook can move to, rather than just counting captures.