LeetCode Solutions Blog

Available Captures for Rook

Number: 1041

Difficulty: Easy

Paid? No

Companies: Block

Problem Description

Given an 8x8 chessboard represented as a matrix, determine the number of black pawns ('p') that a white rook ('R') can capture in one move. The rook can move horizontally or vertically in straight lines until it is blocked by another piece (bishop 'B' or any pawn) or the edge of the board.

Key Insights

The board is fixed in size (8x8), so a complete scan is efficient.
The first step is to locate the position of the white rook.
From the rook's position, check in the four possible directions (up, down, left, right).
Stop searching in a direction as soon as a bishop is encountered or when encountering a pawn (increment count if pawn found).
Since pieces block the rook’s path, no further moves can be taken past the first encountered piece in any direction.

Space and Time Complexity

Time Complexity: O(1) (The board is always 8x8, so all operations are constant time.) Space Complexity: O(1) (No extra space beyond a few variables is used.)

Solution

We first locate the rook by scanning the board. Then for each of the four directions (up, down, left, right), we iterate from the rook's position until either the edge of the board or a blocking piece is reached. If a pawn is encountered before a blocking bishop, it is captured, and we increment the count. This approach uses a simple simulation technique and iterates over fixed dimensions, making it efficient and easy to understand.

Code Solutions

# Define a function to count the number of captures for the rook on a chessboard.
def numRookCaptures(board):
    # Find the rook's position
    rook_row = rook_col = -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  # Count of pawns that can be captured

    # Define directions: up, down, left, right
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # Iterate over each direction
    for dr, dc in directions:
        r, c = rook_row, rook_col
        # Continue searching in the current direction until we hit the board boundary or a blocking piece.
        while 0 <= r < 8 and 0 <= c < 8:
            # Move one step in the current direction
            r += dr
            c += dc
            if not (0 <= r < 8 and 0 <= c < 8):
                break
            # If a bishop blocks the path, break from this direction.
            if board[r][c] == 'B':
                break
            # If a pawn is found, count the capture and break.
            if board[r][c] == 'p':
                captures += 1
                break
    return captures

# Example test
board = [
    [".",".",".",".",".",".",".","."],
    [".",".",".","p",".",".",".","."],
    [".",".",".","R",".",".",".","p"],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".","p",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."]
]
print(numRookCaptures(board))  # Expected output: 3