#999

Easy

LeetCode Problem Workspace

Available Captures for Rook

This problem involves finding the number of pawns a rook can capture on a chessboard, considering obstacles like bishops and boundaries.

array matrix simulation

Problem Statement

You are given an 8x8 matrix representing a chessboard. The board includes a 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 horizontally or vertically any number of squares until it reaches another piece or the edge of the board. The rook attacks a pawn if it can reach the pawn's square in one move, without any pieces blocking the path. Return the number of pawns the rook can attack.

Examples

Example 1

Input: board = [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]

Output: 3

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

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

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'

Solution Approach

Simulate Rook's Movement

To solve the problem, simulate the rook's movement in the four cardinal directions (up, down, left, right). For each direction, check if there are any obstacles (bishops or boundaries) that block the rook's path. If a pawn is found in the path, count it as a valid capture.

Track Boundaries and Obstacles

For each direction the rook moves, ensure that its movement is bounded by the edges of the chessboard and blocked by any other pieces (bishops or pawns). As soon as an obstacle is encountered, stop checking further in that direction.

Count Captures

Whenever a pawn ('p') is found in the rook's path, increment the capture count. The final result is the total number of pawns the rook can attack.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution depends on the size of the board and the number of pieces. In this case, the board is fixed at 8x8, so we can consider the time complexity to be O(1), as the rook checks up to four directions. The space complexity is also O(1) as we only need a constant amount of extra space to keep track of the rook's position and potential captures.

What Interviewers Usually Probe

Tests candidate's ability to simulate piece movements in a grid-based problem.
Evaluates problem-solving with matrix traversal and handling of obstacles.
Checks for clarity in handling edge cases like pieces blocking the path.

Common Pitfalls or Variants

Common pitfalls

Not accounting for bishops blocking the rook's path, leading to incorrect captures.
Failing to stop when encountering a boundary or obstacle, allowing false positives for captures.
Overcomplicating the solution by not taking advantage of the fixed 8x8 grid size.

Follow-up variants

Modify the problem to include multiple rooks and calculate all possible captures.
Implement the solution on larger boards (e.g., 10x10) and handle boundary conditions.
Change the problem to count the number of squares the rook can move to, rather than just counting captures.

FAQ

How can I efficiently count the number of pawns a rook can capture?

Simulate the rook's movement in four directions (up, down, left, right) and check for pawns until an obstacle (bishop or edge) is encountered.

What should I do if the rook is blocked by a bishop?

If the rook encounters a bishop, stop moving in that direction as the bishop blocks further captures.

Can I optimize the solution for larger chessboards?

For larger boards, adjust the traversal logic to handle larger grid sizes, but the core approach remains the same.

What edge cases should I consider when solving this problem?

Consider edge cases where the rook is surrounded by bishops or positioned near the edges of the board.

How does GhostInterview help with solving problems like this?

GhostInterview helps by breaking down the problem into manageable steps, pointing out common pitfalls, and offering optimization strategies.

terminal

Solution

Solution 1: Simulation

We first traverse the board to find the position of the rook $(i, j)$. Then, starting from $(i, j)$, we traverse in four directions: up, down, left, and right.

class Solution:
    def numRookCaptures(self, board: List[List[str]]) -> int:
        dirs = (-1, 0, 1, 0, -1)
        n = len(board)
        for i in range(n):
            for j in range(n):
                if board[i][j] == "R":
                    ans = 0
                    for a, b in pairwise(dirs):
                        x, y = i + a, j + b
                        while 0 <= x < n and 0 <= y < n and board[x][y] != "B":
                            if board[x][y] == "p":
                                ans += 1
                                break
                            x, y = x + a, y + b
                    return ans

Continue Practicing

#885 spiral matrix iii #867 transpose matrix #832 flipping an image