跳至主要內容

999. 可以被一步捕获的棋子数


999. 可以被一步捕获的棋子数

🟢   🔖  数组 矩阵 模拟  🔗 力扣open in new window LeetCodeopen in new window

题目

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 的卒。

提示:

  1. board.length == 8
  2. board[i].length == 8
  3. board[i][j] 可以是 'R''.''B''p'
  4. 只有一个格子上存在 board[i][j] == 'R'

解题思路

  1. 遍历整个棋盘,记录 R 的位置 (x, y)

  2. 使用方向数组 [[1, 0], [-1, 0], [0, 1], [0, -1]],分别表示下、上、右、左四个方向。

  3. R 的位置出发,按照每个方向依次移动,每次移动时:

    • 如果遇到卒 p,捕获并停止该方向的移动。
    • 如果遇到象 B 或出界,停止该方向的移动。
    • 如果遇到空格 .,继续移动。
  4. 返回捕获的卒数量。

复杂度分析

  • 时间复杂度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统计网格图中没有被保卫的格子数[✓]数组 矩阵 模拟🟠🀄️open in new window 🔗open in new window
3001捕获黑皇后需要的最少移动次数数组 枚举🟠🀄️open in new window 🔗open in new window
3256放三个车的价值之和最大 I数组 动态规划 枚举 1+🔴🀄️open in new window 🔗open in new window
3257放三个车的价值之和最大 II数组 动态规划 枚举 1+🔴🀄️open in new window 🔗open in new window