题目描述
给定一个 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'
解法
方法一：模拟
我们先遍历棋盘，找到车的位置 $(i, j)$，然后从 $(i, j)$ 出发，向上下左右四个方向遍历：
- 如果不是边界且不是象，则继续向前走；
- 如果是卒，则答案加一，并停止该方向的遍历。
遍历完四个方向后，即可得到答案。
时间复杂度 $O(m \times n)$，其中 $m$ 和 $n$ 分别是棋盘的行数和列数，本题中 $m = n = 8$。空间复杂度 $O(1)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | class Solution {
public int numRookCaptures(char[][] board) {
final int[] dirs = {-1, 0, 1, 0, -1};
int n = board.length;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == 'R') {
int ans = 0;
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
while (x >= 0 && x < n && y >= 0 && y < n && board[x][y] != 'B') {
if (board[x][y] == 'p') {
++ans;
break;
}
x += dirs[k];
y += dirs[k + 1];
}
}
return ans;
}
}
}
return 0;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | class Solution {
public:
int numRookCaptures(vector<vector<char>>& board) {
const int dirs[5] = {-1, 0, 1, 0, -1};
int n = board.size();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == 'R') {
int ans = 0;
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
while (x >= 0 && x < n && y >= 0 && y < n && board[x][y] != 'B') {
if (board[x][y] == 'p') {
++ans;
break;
}
x += dirs[k];
y += dirs[k + 1];
}
}
return ans;
}
}
}
return 0;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | func numRookCaptures(board [][]byte) (ans int) {
dirs := []int{-1, 0, 1, 0, -1}
n := len(board)
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if board[i][j] == 'R' {
for k := 0; k < 4; k++ {
x, y := i + dirs[k], j + dirs[k+1]
for x >= 0 && x < n && y >= 0 && y < n && board[x][y] != 'B' {
if board[x][y] == 'p' {
ans++
break
}
x += dirs[k]
y += dirs[k+1]
}
}
return
}
}
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | function numRookCaptures(board: string[][]): number {
const dirs = [-1, 0, 1, 0, -1];
const n = board.length;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (board[i][j] === 'R') {
let ans = 0;
for (let k = 0; k < 4; k++) {
let [x, y] = [i + dirs[k], j + dirs[k + 1]];
while (x >= 0 && x < n && y >= 0 && y < n && board[x][y] !== 'B') {
if (board[x][y] === 'p') {
ans++;
break;
}
x += dirs[k];
y += dirs[k + 1];
}
}
return ans;
}
}
}
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | impl Solution {
pub fn num_rook_captures(board: Vec<Vec<char>>) -> i32 {
let dirs = [-1, 0, 1, 0, -1];
let n = board.len();
for i in 0..n {
for j in 0..n {
if board[i][j] == 'R' {
let mut ans = 0;
for k in 0..4 {
let mut x = i as i32 + dirs[k];
let mut y = j as i32 + dirs[k + 1];
while x >= 0
&& x < n as i32
&& y >= 0
&& y < n as i32
&& board[x as usize][y as usize] != 'B'
{
if board[x as usize][y as usize] == 'p' {
ans += 1;
break;
}
x += dirs[k];
y += dirs[k + 1];
}
}
return ans;
}
}
}
0
}
}
|