999. Available Captures for Rook

Problem

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.

https://leetcode.cn/problems/available-captures-for-rook/

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'

Test Cases

1
2

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import pytest

from solution import Solution


@pytest.mark.parametrize('board, expected', [
    (
        [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]],
        3
    ),
    (
        [[".",".",".",".",".",".",".","."],[".","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
    ),
    (
        [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","p",".",".",".","."],["p","p",".","R",".","p","B","."],[".",".",".",".",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."]],
        3
    ),
])
class Test:
    def test_solution(self, board, expected):
        sol = Solution()
        assert sol.numRookCaptures(board) == expected

Thoughts

先找到 white rook 的位置，记为 (r0, c0)。从此位置开始，往上下左右四个方向逐格遍历，直到超出边界或遇到其他棋子。如果遇到的是 black pawns 则计数加一。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def numRookCaptures(self, board: list[list[str]]) -> int:
        n = len(board)
        r0, c0 = next((r, c) for r in range(n) for c in range(n) if board[r][c] == 'R')
        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        cnt = 0
        for dr, dc in dirs:
            r, c = r0, c0
            while True:
                r += dr
                c += dc
                if not (0 <= r < n and 0 <= c < n):
                    break
                elif board[r][c] == 'p':
                    cnt += 1
                    break
                elif board[r][c] != '.':
                    break

        return cnt

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章