Solution Explanation: Available Captures for Rook

This problem involves finding the number of pawns a rook can capture on a chessboard. The solution uses a simulation approach to explore the rook's possible movements.

Approach:

1. Find the Rook: The algorithm first iterates through the chessboard (board) to locate the position of the rook ('R').

2. Directional Traversal: Once the rook's position is found, it explores the four cardinal directions (up, down, left, right) using a loop. The dirs array in the code efficiently handles direction changes.

3. Path Checking: For each direction:

   • It checks if the current position is within the board's boundaries.
   • It checks if the current square is occupied by a bishop ('B'). If it is, the rook's movement in that direction is blocked, and the traversal stops.
   • If the square is occupied by a pawn ('p'), the rook can capture it, so a counter (ans) is incremented, and the traversal in that direction stops.
   • If the square is empty ('.') the traversal continues to the next square in the same direction.

4. Return the Count: After checking all four directions, the function returns the total number of captured pawns (ans).

Time Complexity Analysis:

The algorithm iterates through the board once to find the rook (O(N^2), where N is the size of the board, which is 8x8 in this case). Then, for each direction, it traverses at most N steps. Since there are four directions, the maximum number of squares checked is 4N. Therefore, the overall time complexity is O(N^2), which simplifies to O(1) because N is a constant (8). The time complexity is dominated by the initial search for the rook.

Space Complexity Analysis:

The algorithm uses a constant amount of extra space to store variables such as ans, i, j, k, x, y, and the dirs array. This means the space complexity is O(1).

Code Explanation (Python Example):

class Solution:
    def numRookCaptures(self, board: List[List[str]]) -> int:
        dirs = [-1, 0, 1, 0, -1] # directions: up, right, down, left.  The last -1 is for indexing
        n = len(board)
        for i in range(n):
            for j in range(n):
                if board[i][j] == "R":
                    ans = 0
                    for k in range(4): # Iterate through directions
                        x, y = i + dirs[k], j + dirs[k+1] # Calculate next position
                        while 0 <= x < n and 0 <= y < n and board[x][y] != "B": # Check boundaries and bishop
                            if board[x][y] == "p":
                                ans += 1
                                break # Pawn captured, stop traversal in this direction
                            x, y = x + dirs[k], y + dirs[k+1] # Move to the next square
                    return ans

The other language examples follow the same logic; only syntax varies. The dirs array cleverly handles moving in four directions using a single loop. The while loop efficiently checks for boundary conditions and obstructions.