999. 可以被一步捕获的棋子数
999. 可以被一步捕获的棋子数
题目
You are given an 8 x 8
matrix representing a chessboard. There is exactly one white rook represented by 'R'
, some number of white bishops 'B'
, and some number of black pawns 'p'
. Empty squares are represented by '.'
.
A rook can move any number of squares horizontally or vertically (up, down, left, right) until it reaches another piece or the edge of the board. A rook is attacking a pawn if it can move to the pawn's square in one move.
Note: A rook cannot move through other pieces, such as bishops or pawns. This means a rook cannot attack a pawn if there is another piece blocking the path.
Return the number of pawns the white rook is attacking.
Example 1:
Input:
board = [[".",".",".",".",".",".",".","."], [".",".",".","p",".",".",".","."], [".",".",".","R",".",".",".","p"], [".",".",".",".",".",".",".","."], [".",".",".",".",".",".",".","."], [".",".",".","p",".",".",".","."], [".",".",".",".",".",".",".","."], [".",".",".",".",".",".",".","."]]
Output: 3
Explanation:
In this example, the rook is attacking all the pawns.
Example 2:
Input:
board = [[".",".",".",".",".",".","."], [".","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",".","."], [".",".",".",".",".",".",".","."], [".",".",".",".",".",".",".","."]]
Output: 0
Explanation:
The bishops are blocking the rook from attacking any of the pawns.
Example 3:
Input:
board = [[".",".",".",".",".",".",".","."], [".",".",".","p",".",".",".","."], [".",".",".","p",".",".",".","."], ["p","p",".","R",".","p","B","."], [".",".",".",".",".",".",".","."], [".",".",".","B",".",".",".","."], [".",".",".","p",".",".",".","."], [".",".",".",".",".",".",".","."]]
Output: 3
Explanation:
The rook is attacking the pawns at positions b5, d6, and f5.
Constraints:
board.length == 8
board[i].length == 8
board[i][j]
is either'R'
,'.'
,'B'
, or'p'
- There is exactly one cell with
board[i][j] == 'R'
题目大意
给定一个 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 == 8
board[i].length == 8
board[i][j]
可以是'R'
,'.'
,'B'
或'p'
- 只有一个格子上存在
board[i][j] == 'R'
解题思路
遍历整个棋盘,记录
R
的位置(x, y)
。使用方向数组
[[1, 0], [-1, 0], [0, 1], [0, -1]]
,分别表示下、上、右、左四个方向。从
R
的位置出发,按照每个方向依次移动,每次移动时:- 如果遇到卒
p
,捕获并停止该方向的移动。 - 如果遇到象
B
或出界,停止该方向的移动。 - 如果遇到空格
.
,继续移动。
- 如果遇到卒
返回捕获的卒数量。
复杂度分析
时间复杂度:
O(1)
- 找到车的位置需要遍历整个棋盘,时间复杂度为
O(64)
(固定为 8x8 棋盘)。 - 模拟四个方向的移动,每个方向最多遍历 8 格,时间复杂度为
O(4 × 8)
。 - 总时间复杂度为
O(64)
,即常数时间。
- 找到车的位置需要遍历整个棋盘,时间复杂度为
空间复杂度:
O(1)
,使用常数额外空间。
代码
/**
* @param {character[][]} board
* @return {number}
*/
var numRookCaptures = function (board) {
let x = 0,
y = 0,
res = 0;
// 找到车 'R' 的位置
for (let i = 0; i < 8; i++) {
for (let j = 0; j < 8; j++) {
if (board[i][j] === 'R') {
x = i;
y = j;
break;
}
}
}
// 定义四个方向
const direction = [
[1, 0],
[-1, 0],
[0, 1],
[0, -1]
];
// 遍历四个方向
for (let [dx, dy] of direction) {
let i = x + dx,
j = y + dy;
while (i >= 0 && i < 8 && j >= 0 && j < 8) {
if (board[i][j] === 'p') {
// 如果遇到卒
res++;
break;
}
if (board[i][j] !== '.') {
// 如果遇到阻挡(非空格)
break;
}
i += dx;
j += dy;
}
}
return res;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
2257 | 统计网格图中没有被保卫的格子数 | [✓] | 数组 矩阵 模拟 | 🟠 | 🀄️ 🔗 |
3001 | 捕获黑皇后需要的最少移动次数 | 数组 枚举 | 🟠 | 🀄️ 🔗 | |
3256 | 放三个车的价值之和最大 I | 数组 动态规划 枚举 1+ | 🔴 | 🀄️ 🔗 | |
3257 | 放三个车的价值之和最大 II | 数组 动态规划 枚举 1+ | 🔴 | 🀄️ 🔗 |