题目描述

给定一个 8 x 8 的棋盘，只有一个 白色的车，用字符 'R' 表示。棋盘上还可能存在白色的象 'B' 以及黑色的卒 'p'。空方块用字符 '.' 表示。

车可以按水平或竖直方向（上，下，左，右）移动任意个方格直到它遇到另一个棋子或棋盘的边界。如果它能够在一次移动中移动到棋子的方格，则能够 吃掉 棋子。

注意：车不能穿过其它棋子，比如象和卒。这意味着如果有其它棋子挡住了路径，车就不能够吃掉棋子。

返回白车 攻击 范围内 兵的数量。

思路

• 车能攻击到的车最多4个，上下左右各一个。
• 先遍历棋盘board，找到'车'的位置(x0, y0)。
• 再让车在上下左右四个方向进行遍历，若当前节点的横纵坐标在[0, 7]范围内，且此节点值为'.',则继续在该方向上遍历。
• 在每个方向上停留的最后节点，要么是第一个非'.'节点，此时判断其是否为'p'即可，若为'.'则答案加1，要么是已遍历出界。

Python代码

class Solution:
    def numRookCaptures(self, board: List[List[str]]) -> int:
        size = 8
        for i in range(8):
            for j in range(8):
                if board[i][j] == 'R':
                    x0, y0 = i, j
                    break
        ans = 0
        for dx, dy in (0, 1), (0, -1), (-1, 0), (1, 0):
            x, y = x0 + dx, y0 + dy
            while 0 <= x < size and 0 <= y < size and board[x][y] == '.':
                x = x + dx
                y = y + dy
            if 0 <= x < size and 0 <= y < size and board[x][y] == 'p':
                ans = ans + 1
        return ans

复杂度分析

• 时间复杂度：$O(n^2)$ ,$n$ 为8。
• 空间复杂度：$O(1)$。