LeetCode 999: Available Captures for Rook (Directional Scan)
LeetCode 999MatrixSimulationToday we solve LeetCode 999 - Available Captures for Rook.
Source: https://leetcode.com/problems/available-captures-for-rook/
English
Problem Summary
Given an 8x8 chessboard, count how many pawns a rook can capture in one move. The rook moves in four directions, stops at bishops, and can capture at most one pawn per direction.
Key Insight
After locating the rook, we only need to scan four straight lines (up, down, left, right). In each direction, the first non-empty square decides the result: bishop blocks, pawn adds one capture, otherwise keep moving.
Algorithm
- Find rook position R.
- For each direction, step cell by cell until out of board.
- If bishop B appears: stop this direction.
- If pawn p appears: count +1 and stop this direction.
Complexity Analysis
Board size is fixed (8x8).
Time: O(64).
Space: O(1).
Common Pitfalls
- Forgetting to stop after first pawn in a direction.
- Letting rook move through bishop.
- Not handling rook location correctly before scanning.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int numRookCaptures(char[][] board) {
int rx = -1, ry = -1;
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if (board[i][j] == 'R') {
rx = i;
ry = j;
}
}
}
int ans = 0;
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int[] d : dirs) {
int x = rx + d[0], y = ry + d[1];
while (x >= 0 && x < 8 && y >= 0 && y < 8) {
if (board[x][y] == 'B') break;
if (board[x][y] == 'p') {
ans++;
break;
}
x += d[0];
y += d[1];
}
}
return ans;
}
}func numRookCaptures(board [][]byte) int {
rx, ry := -1, -1
for i := 0; i < 8; i++ {
for j := 0; j < 8; j++ {
if board[i][j] == 'R' {
rx, ry = i, j
}
}
}
ans := 0
dirs := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
for _, d := range dirs {
x, y := rx+d[0], ry+d[1]
for x >= 0 && x < 8 && y >= 0 && y < 8 {
if board[x][y] == 'B' {
break
}
if board[x][y] == 'p' {
ans++
break
}
x += d[0]
y += d[1]
}
}
return ans
}class Solution {
public:
int numRookCaptures(vector<vector<char>>& board) {
int rx = -1, ry = -1;
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if (board[i][j] == 'R') {
rx = i;
ry = j;
}
}
}
int ans = 0;
int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (auto& d : dirs) {
int x = rx + d[0], y = ry + d[1];
while (x >= 0 && x < 8 && y >= 0 && y < 8) {
if (board[x][y] == 'B') break;
if (board[x][y] == 'p') {
ans++;
break;
}
x += d[0];
y += d[1];
}
}
return ans;
}
};class Solution:
def numRookCaptures(self, board: List[List[str]]) -> int:
rx = ry = -1
for i in range(8):
for j in range(8):
if board[i][j] == 'R':
rx, ry = i, j
ans = 0
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
x, y = rx + dx, ry + dy
while 0 <= x < 8 and 0 <= y < 8:
if board[x][y] == 'B':
break
if board[x][y] == 'p':
ans += 1
break
x += dx
y += dy
return ans/**
* @param {character[][]} board
* @return {number}
*/
var numRookCaptures = function(board) {
let rx = -1, ry = -1;
for (let i = 0; i < 8; i++) {
for (let j = 0; j < 8; j++) {
if (board[i][j] === 'R') {
rx = i;
ry = j;
}
}
}
let ans = 0;
const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
for (const [dx, dy] of dirs) {
let x = rx + dx, y = ry + dy;
while (x >= 0 && x < 8 && y >= 0 && y < 8) {
if (board[x][y] === 'B') break;
if (board[x][y] === 'p') {
ans++;
break;
}
x += dx;
y += dy;
}
}
return ans;
};中文
题目概述
给你一个 8x8 的棋盘，统计车 R 一步内最多能吃掉多少个兵 p。车可以沿四个方向直线移动，遇到象 B 会被阻挡，每个方向最多吃到一个兵。
核心思路
先找到车的位置，然后分别向上、下、左、右做直线扫描。每个方向遇到的第一个非空格子决定结果，遇到象就停止，遇到兵就计数并停止。
算法步骤
- 先定位 R 的坐标。
- 对四个方向逐格前进，直到越界。
- 遇到 B：当前方向结束。
- 遇到 p：答案加一并结束当前方向。
复杂度分析
棋盘大小固定为 8x8。
时间复杂度：O(64)。
空间复杂度：O(1)。
常见陷阱
- 某方向吃到兵后没有停止，导致重复计数。
- 让车错误穿过象。
- 没先正确找到车的位置就开始扫描。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int numRookCaptures(char[][] board) {
int rx = -1, ry = -1;
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if (board[i][j] == 'R') {
rx = i;
ry = j;
}
}
}
int ans = 0;
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int[] d : dirs) {
int x = rx + d[0], y = ry + d[1];
while (x >= 0 && x < 8 && y >= 0 && y < 8) {
if (board[x][y] == 'B') break;
if (board[x][y] == 'p') {
ans++;
break;
}
x += d[0];
y += d[1];
}
}
return ans;
}
}func numRookCaptures(board [][]byte) int {
rx, ry := -1, -1
for i := 0; i < 8; i++ {
for j := 0; j < 8; j++ {
if board[i][j] == 'R' {
rx, ry = i, j
}
}
}
ans := 0
dirs := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
for _, d := range dirs {
x, y := rx+d[0], ry+d[1]
for x >= 0 && x < 8 && y >= 0 && y < 8 {
if board[x][y] == 'B' {
break
}
if board[x][y] == 'p' {
ans++
break
}
x += d[0]
y += d[1]
}
}
return ans
}class Solution {
public:
int numRookCaptures(vector<vector<char>>& board) {
int rx = -1, ry = -1;
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if (board[i][j] == 'R') {
rx = i;
ry = j;
}
}
}
int ans = 0;
int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (auto& d : dirs) {
int x = rx + d[0], y = ry + d[1];
while (x >= 0 && x < 8 && y >= 0 && y < 8) {
if (board[x][y] == 'B') break;
if (board[x][y] == 'p') {
ans++;
break;
}
x += d[0];
y += d[1];
}
}
return ans;
}
};class Solution:
def numRookCaptures(self, board: List[List[str]]) -> int:
rx = ry = -1
for i in range(8):
for j in range(8):
if board[i][j] == 'R':
rx, ry = i, j
ans = 0
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
x, y = rx + dx, ry + dy
while 0 <= x < 8 and 0 <= y < 8:
if board[x][y] == 'B':
break
if board[x][y] == 'p':
ans += 1
break
x += dx
y += dy
return ans/**
* @param {character[][]} board
* @return {number}
*/
var numRookCaptures = function(board) {
let rx = -1, ry = -1;
for (let i = 0; i < 8; i++) {
for (let j = 0; j < 8; j++) {
if (board[i][j] === 'R') {
rx = i;
ry = j;
}
}
}
let ans = 0;
const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
for (const [dx, dy] of dirs) {
let x = rx + dx, y = ry + dy;
while (x >= 0 && x < 8 && y >= 0 && y < 8) {
if (board[x][y] === 'B') break;
if (board[x][y] === 'p') {
ans++;
break;
}
x += dx;
y += dy;
}
}
return ans;
};
Comments