可以被一步捕获的棋子数

难度: Easy

在一个 8 x 8 的棋盘上，有一个白色的车（Rook），用字符 'R' 表示。棋盘上还可能存在空方块，白色的象（Bishop）以及黑色的卒（pawn），分别用字符 '.'，'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 == board[i].length == 8
board[i][j] 可以是 'R'，'.'，'B' 或 'p'
只有一个格子上存在 board[i][j] == 'R'

Submission

运行时间: 25 ms

内存: 16.1 MB

class Solution:
    def numRookCaptures(self, board: List[List[str]]) -> int:
        row, col = '', ''

        for i in board:
            row += ''.join(i)
            row += ','
        
        for j in range(8):
            for k in range(8):
                col += board[k][j]
            col += ','

        s = row + col
        s = s.replace('.', '')

        return s.count('pR') + s.count('Rp')

Explain

该题解的主要思路是首先将棋盘的行和列转化为字符串形式，然后组合到一起，形成一个单一的长字符串。接着，通过删除所有表示空格的'.'字符，使得字符串中只剩下棋子的字符。这样，'pR'和'Rp'将直接表示车（Rook）能够捕获的黑卒（pawn）的情况，即这两种组合分别代表黑卒在车的左侧或右侧，上侧或下侧。最后，统计这两种组合在字符串中出现的次数之和，即为答案。

时间复杂度: O(1)

空间复杂度: O(1)

class Solution:
    def numRookCaptures(self, board: List[List[str]]) -> int:
        row, col = '', ''

        # 构建行信息的字符串，每行之后添加一个分隔符','
        for i in board:
            row += ''.join(i)
            row += ','
        
        # 构建列信息的字符串，每列之后添加一个分隔符','
        for j in range(8):
            for k in range(8):
                col += board[k][j]
            col += ','

        # 合并行和列信息，形成单一字符串，并移除所有空格字符
        s = row + col
        s = s.replace('.', '')

        # 计算可以直接捕获的黑卒的数量
        return s.count('pR') + s.count('Rp')

Explore

在算法中使用字符串而不是列表或数组的主要原因是字符串提供了更为直接的方式来进行特定模式（如'pR'或'Rp'）的搜索和计数。由于字符串在Python中支持高效的内建操作如join、replace和count，这使得处理和分析棋盘的行和列数据更加便捷。此外，字符串的不可变性也避免了在操作过程中不小心修改数据的风险。

移除所有的'.'字符（代表空格）的主要目的是简化字符串，从而仅保留棋子的信息。这样做可以减少数据量，优化搜索和计数操作的效率。因为空格对于判断车是否可以捕获卒没有直接影响，所以移除它们可以使得字符串中只包含有效的、需要考虑的棋子字符，从而直接关注于'Rook'和'pawn'的相对位置模式。

实际上，题解中的方法没有直接处理棋子之间是否被阻挡的情况。它仅通过统计字符串中'pR'和'Rp'的出现次数来判断可以直接捕获的卒。这种方法假设了在'Rook'和'pawn'之间没有其他棋子，是一种简化的处理方式。如果需要精确处理棋子之间的阻挡情况，则需要在字符串处理前首先验证'Rook'与'pawn'之间的路径上是否存在其他棋子。

使用逗号作为分隔符是为了在处理过程中清晰地区分各行和各列的边界，防止行末尾和列开头的字符被错误地连在一起处理。虽然这种方法在大多数情况下是有效的，确实存在一定的风险，特别是如果不小心处理分隔符，可能会引起解析错误。然而，在该算法的上下文中，由于棋盘的大小和结构是固定的（8x8），使用逗号作为分隔符带来的复杂性和风险是可控的。