Easy

题目描述

给你一个 8 x 8 的棋盘，上面有一个白色车用 ‘R’ 表示，一些白色象用 ‘B’ 表示，还有一些黑色兵用 ‘p’ 表示。空白格子用 ‘.’ 表示。

车可以按水平或竖直方向（上下左右）移动任意数量的格子，直到它到达另一个棋子或棋盘的边缘。如果车能够在一步内移动到兵的位置，那么车就在攻击这个兵。

注意：车不能穿过其他棋子，比如象或兵。这意味着如果路径上有其他棋子阻挡，车就无法攻击兵。

返回白色车正在攻击的兵的数量。

示例 1：

输入：board = [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
输出：3
解释：在这个例子中，车正在攻击所有的兵。

示例 2：

输入：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",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
输出：0
解释：象阻挡了车攻击任何兵。

示例 3：

输入：board = [[".",".",".",".",".",".",".","."],[".",".",".","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'

解题思路

这道题是一个简单的模拟题，需要找到车的位置，然后向四个方向搜索可以攻击的兵。

解题思路：

  1. 找到车的位置：遍历整个棋盘，找到 ‘R’ 所在的位置作为起点。

  2. 四方向搜索：从车的位置出发，分别向上、下、左、右四个方向进行搜索。

  3. 搜索规则：

    • 如果遇到空格 ‘.’，继续向该方向搜索
    • 如果遇到黑色兵 ‘p’，计数加1，停止该方向的搜索
    • 如果遇到白色象 ‘B’，停止该方向的搜索（被阻挡）
    • 如果到达棋盘边界，停止该方向的搜索

  4. 返回结果：四个方向搜索完成后，返回找到的兵的总数。

这个问题的关键是理解车的移动规则：车可以沿直线移动，但不能穿过其他棋子。因此我们需要在每个方向上逐格检查，直到遇到障碍物或边界。

算法步骤：

  • 时间复杂度：O(1)，因为棋盘大小固定为8x8
  • 空间复杂度：O(1)，只使用了常数额外空间

代码实现

class Solution {
public:
    int numRookCaptures(vector<vector<char>>& board) {
        int rookRow = -1, rookCol = -1;
        
        // 找到车的位置
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (board[i][j] == 'R') {
                    rookRow = i;
                    rookCol = j;
                    break;
                }
            }
            if (rookRow != -1) break;
        }
        
        int captures = 0;
        // 四个方向：上、下、左、右
        int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        for (int d = 0; d < 4; d++) {
            int dx = directions[d][0];
            int dy = directions[d][1];
            int x = rookRow + dx;
            int y = rookCol + dy;
            
            while (x >= 0 && x < 8 && y >= 0 && y < 8) {
                if (board[x][y] == 'p') {
                    captures++;
                    break;
                } else if (board[x][y] == 'B') {
                    break;
                }
                x += dx;
                y += dy;
            }
        }
        
        return captures;
    }
};

class Solution:
    def numRookCaptures(self, board: List[List[str]]) -> int:
        # 找到车的位置
        rook_row, rook_col = -1, -1
        for i in range(8):
            for j in range(8):
                if board[i][j] == 'R':
                    rook_row, rook_col = i, j
                    break
            if rook_row != -1:
                break
        
        captures = 0
        # 四个方向：上、下、左、右
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        for dx, dy in directions:
            x, y = rook_row + dx, rook_col + dy
            
            while 0 <= x < 8 and 0 <= y < 8:
                if board[x][y] == 'p':
                    captures += 1
                    break
                elif board[x][y] == 'B':
                    break
                x += dx
                y += dy
        
        return captures

public class Solution {
    public int NumRookCaptures(char[][] board) {
        int rookRow = -1, rookCol = -1;
        
        // 找到车的位置
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (board[i][j] == 'R') {
                    rookRow = i;
                    rookCol = j;
                    break;
                }
            }
            if (rookRow != -1) break;
        }
        
        int captures = 0;
        // 四个方向：上、下、左、右
        int[,] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        for (int d = 0; d < 4; d++) {
            int dx = directions[d, 0];
            int dy = directions[d, 1];
            int x = rookRow + dx;
            int y = rookCol + dy;
            
            while (x >= 0 && x < 8 && y >= 0 && y < 8) {
                if (board[x][y] == 'p') {
                    captures++;
                    break;
                } else if (board[x][y] == 'B') {
                    break;
                }
                x += dx;
                y += dy;
            }
        }
        
        return captures;
    }
}

/**
 * @param {character[][]} board
 * @return {number}
 */
var numRookCaptures = function(board) {
    let rookRow = -1, rookCol = -1;
    
    // Find the rook position
    for (let i = 0; i < 8; i++) {
        for (let j = 0; j < 8; j++) {
            if (board[i][j] === 'R') {
                rookRow = i;
                rookCol = j;
                break;
            }
        }
        if (rookRow !== -1) break;
    }
    
    let captures = 0;
    const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]; // right, left, down, up
    
    // Check all four directions
    for (let [dx, dy] of directions) {
        let x = rookRow + dx;
        let y = rookCol + dy;
        
        while (x >= 0 && x < 8 && y >= 0 && y < 8) {
            if (board[x][y] === 'p') {
                captures++;
                break;
            } else if (board[x][y] === 'B') {
                break;
            }
            x += dx;
            y += dy;
        }
    }
    
    return captures;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(1)棋盘大小固定为8x8，最多遍历64个格子
空间复杂度O(1)只使用了常数额外空间存储方向数组和变量

相关题目