Problem Description

The Leetcode problem "Available Captures for Rook" presents an 8x8 chessboard, represented as a 2D character array board. The board may contain the following pieces:

• 'R': White Rook (exactly one on the board)
• 'B': Black Bishop (zero or more)
• 'p': Black Pawn (zero or more)
• '.': Empty square

Key constraints:

• There is exactly one white rook on the board.
• The rook cannot move through bishops or off the board.
• Each pawn can be captured at most once (do not count the same pawn multiple times).

Thought Process

To solve this problem, the first step is to identify the location of the rook on the board. Since there is exactly one rook, we can scan the board to find its coordinates. Once located, we need to consider each of the four possible directions the rook can move: up, down, left, and right.

For each direction, the rook moves one square at a time:

• If it encounters a bishop ('B'), it cannot move further in that direction.
• If it encounters a pawn ('p'), it can capture the pawn (count it), but cannot move further in that direction.
• If it encounters an empty square ('.'), it continues moving in that direction.
• If it reaches the edge of the board, it stops.

A brute-force approach would be to check every square in each direction until an obstacle is found. Since the board is always 8x8, this is efficient enough, but we can further optimize by stopping as soon as we hit a bishop or pawn.

Solution Approach

Let's break down the solution step by step:

1. Locate the Rook:
   • Iterate through all rows and columns of the board to find the coordinates (rook_row, rook_col) where board[rook_row][rook_col] == 'R'.
2. Define Directions:
   • Set up a list of direction vectors for up, down, left, and right: [(-1,0), (1,0), (0,-1), (0,1)].
3. Check Each Direction:
   • For each direction, move step by step from the rook's position.
   • If the next cell is a bishop ('B'), stop checking in this direction.
   • If the next cell is a pawn ('p'), increment the capture count and stop checking further in this direction.
   • If the next cell is empty ('.'), continue moving in the same direction.
   • Repeat until you hit the edge of the board.
4. Return the Result:
   • Sum up the captures from all four directions and return the total.

Example Walkthrough

Consider the following board:

    [
      [".",".",".",".",".",".",".","."],
      [".",".",".","p",".",".",".","."],
      [".",".",".","R",".",".",".","p"],
      [".",".",".",".",".",".",".","."],
      [".",".",".",".",".",".",".","."],
      [".",".",".","p",".",".",".","."],
      [".",".",".",".",".",".",".","."],
      [".",".",".",".",".",".",".","."]
    ]
    

1. Locate the Rook: It's at position (2,3).
2. Check Upwards:
   • Move to (1,3): it's a pawn ('p'). Capture it and stop.
3. Check Downwards:
   • Move to (3,3): empty.
   • Move to (4,3): empty.
   • Move to (5,3): pawn ('p'). Capture it and stop.
4. Check Left:
   • Move to (2,2): empty.
   • Move to (2,1): empty.
   • Move to (2,0): empty. Reached the edge, stop.
5. Check Right:
   • Move to (2,4): empty.
   • Move to (2,5): empty.
   • Move to (2,6): empty.
   • Move to (2,7): pawn ('p'). Capture it and stop.

Total captures: 3 pawns (up, down, right).

Time and Space Complexity

Brute-Force Approach:

• Time Complexity: O(1), since the board size is fixed at 8x8, and the number of steps is bounded.
• Space Complexity: O(1), as we use only a few variables for position and counting.

• Time Complexity: O(1), for the same reasons—no matter the input, the maximum steps are constant.
• Space Complexity: O(1), since no auxiliary data structures are required.

The solution is efficient and scalable due to the small, fixed size of the chessboard.

Summary

The "Available Captures for Rook" problem is a straightforward simulation of chess movement. By first locating the rook and then scanning in each direction until a pawn or bishop is encountered, we efficiently determine the number of pawns the rook can capture in one move. The fixed board size makes this approach both simple and optimal. The key insight is to stop searching a direction as soon as a blocking piece is found, ensuring we never double-count or miss a valid capture.

Code Implementation

class Solution:
    def numRookCaptures(self, board: List[List[str]]) -> int:
        # Locate the rook
        for i in range(8):
            for j in range(8):
                if board[i][j] == 'R':
                    rook_row, rook_col = i, j
                    break

        directions = [(-1,0), (1,0), (0,-1), (0,1)]  # up, down, left, right
        count = 0

        for dr, dc in directions:
            r, c = rook_row, rook_col
            while True:
                r += dr
                c += dc
                if not (0 <= r < 8 and 0 <= c < 8):
                    break
                if board[r][c] == 'B':
                    break
                if board[r][c] == 'p':
                    count += 1
                    break
        return count
      

class Solution {
public:
    int numRookCaptures(vector<vector<char>>& board) {
        int rook_row, rook_col;
        for (int i = 0; i < 8; ++i) {
            for (int j = 0; j < 8; ++j) {
                if (board[i][j] == 'R') {
                    rook_row = i;
                    rook_col = j;
                    break;
                }
            }
        }
        int count = 0;
        vector<pair<int,int>> directions = {{-1,0},{1,0},{0,-1},{0,1}};
        for (auto dir : directions) {
            int r = rook_row, c = rook_col;
            while (true) {
                r += dir.first;
                c += dir.second;
                if (r < 0 || r >= 8 || c < 0 || c >= 8) break;
                if (board[r][c] == 'B') break;
                if (board[r][c] == 'p') {
                    count++;
                    break;
                }
            }
        }
        return count;
    }
};
      

class Solution {
    public int numRookCaptures(char[][] board) {
        int rookRow = 0, rookCol = 0;
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (board[i][j] == 'R') {
                    rookRow = i;
                    rookCol = j;
                    break;
                }
            }
        }
        int[][] directions = {{-1,0},{1,0},{0,-1},{0,1}};
        int count = 0;
        for (int[] dir : directions) {
            int r = rookRow, c = rookCol;
            while (true) {
                r += dir[0];
                c += dir[1];
                if (r < 0 || r >= 8 || c < 0 || c >= 8) break;
                if (board[r][c] == 'B') break;
                if (board[r][c] == 'p') {
                    count++;
                    break;
                }
            }
        }
        return count;
    }
}
      

var numRookCaptures = function(board) {
    let rookRow = 0, rookCol = 0;
    for (let i = 0; i < 8; i++) {
        for (let j = 0; j < 8; j++) {
            if (board[i][j] === 'R') {
                rookRow = i;
                rookCol = j;
                break;
            }
        }
    }
    let directions = [[-1,0],[1,0],[0,-1],[0,1]];
    let count = 0;
    for (let dir of directions) {
        let r = rookRow, c = rookCol;
        while (true) {
            r += dir[0];
            c += dir[1];
            if (r < 0 || r >= 8 || c < 0 || c >= 8) break;
            if (board[r][c] === 'B') break;
            if (board[r][c] === 'p') {
                count++;
                break;
            }
        }
    }
    return count;
};