Leetcode 999. Available Captures for Rook

Problem Explanation

In this problem, we are given an 8 x 8 chessboard with a white rook represented by 'R'. The board may also have empty squares represented by '.', white bishops represented by 'B', and black pawns represented by 'p'. The task is to determine the number of pawns the rook can capture in one move.

The rook can move in four cardinal directions (north, east, west, and south), until it decides to stop, hits the edge of the board or captures a black pawn by moving to its square. However, the rook cannot move to a square occupied by a friendly bishop.

Our goal is to return the number of pawns the rook can capture in one move.

For example, given the following board:

1
2
3[".",".",".",".",".",".",".","."],
4[".",".",".","p",".",".",".","."],
5[".",".",".","R",".",".",".","p"],
6[".",".",".",".",".",".",".","."],
7[".",".",".",".",".",".",".","."],
8[".",".",".","p",".",".",".","."],
9[".",".",".",".",".",".",".","."],
10[".",".",".",".",".",".",".","."]

The rook at position (2,3) can capture the pawns at positions (1,3), (2,7), and (5,3). So the output would be 3.

Solution Approach

This problem can be solved by performing a linear scan of the chessboard from the position of the rook in each of the four directions. The rook's position is first identified by iterating through each cell of the board. Once the rook's position is found, the capturing potential in each direction is calculated.

Capture can only happen if a pawn('p') is encountered before a bishop('B'), while scanning the board linearly in the four directions.

Python Solution

1
2python
3class Solution:
4    def numRookCaptures(self, board):
5        for i in range(8):
6            for j in range(8):
7                # Identify the position of the rook
8                if board[i][j] == 'R':
9                    x,y = i,j
10
11        # direction vectors for north, east, south, west respectively
12        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
13        captures = 0
14
15        for dx, dy in directions:
16            nx, ny = x + dx, y + dy
17            # keep going in one direction until hitting a friendly bishop or edge of board
18            while 0 <= nx < 8 and 0 <= ny < 8 and board[nx][ny] != 'B':
19                if board[nx][ny] == 'p':
20                    captures += 1
21                    break  # stop if encountering a black pawn
22                nx, ny = nx + dx, ny + dy  # continue to the next cell in the current direction
23
24        return captures

Java Solution

1
2java
3public class Solution {
4    public int numRookCaptures(char[][] board) {
5        int captures = 0;
6        int x = 0, y = 0;
7
8        // Identify the position of the Rook
9        for (int i = 0; i < 8; ++i)
10            for (int j = 0; j < 8; ++j)
11                if (board[i][j] == 'R') {
12                    x = i;
13                    y = j;
14                }
15
16        // direction vectors for north, east, south, west respectively
17        int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
18        for (int[] d : directions) {
19            for (int i = x + d[0], j = y + d[1]; 0 <= i && i < 8 && 0 <= j && j < 8; i += d[0], j += d[1]) {
20                if (board[i][j] == 'p') captures++;
21                if (board[i][j] != '.') break;  // stop if encountering a black pawn or bishop
22            }
23        }
24        return captures;
25    }
26}

JavaScript Solution

1
2javascript
3var numRookCaptures = function(board) {
4    let captures = 0;
5    let rookPosition = [0, 0];
6
7    // Identify the position of the rook
8    for(let i=0; i<8; i++){
9        for(let j=0; j<8; j++){
10            if(board[i][j] === 'R'){
11                rookPosition = [i, j];
12            }
13        }
14    }
15
16    let [x, y] = rookPosition;
17
18    // direction vectors for north, east, south, west respectively
19    let directions = [[-1, 0], [0, 1], [1, 0], [0, -1]];
20
21    for(let [dx, dy] of directions){
22        let nx = x + dx;
23        let ny = y + dy;
24
25        // keep going in one direction until hitting friendly bishop or edge of the board
26        while(0 <= nx && nx < 8 && 0 <= ny && ny < 8 && board[nx][ny] !== 'B'){
27            if(board[nx][ny] === 'p'){
28                captures++;
29                break; // stop if encountering a black pawn
30            }
31            nx += dx;
32            ny += dy; // continue in the current direction
33        }
34    }
35
36    return captures;
37};

C++ Solution

1
2C++
3class Solution {
4public:
5    int numRookCaptures(vector<vector<char>>& board) {
6        int captures = 0;
7        int i0 = 0, j0 = 0;
8
9        // Identify the position of the Rook
10        for (int i = 0; i < 8; ++i)
11            for (int j = 0; j < 8; ++j)
12                if (board[i][j] == 'R') {
13                    i0 = i;
14                    j0 = j;
15                }
16
17        // Direction vectors for North, East, South, and West, respectively.
18        vector<vector<int>> directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
19        for (const vector<int>& d : directions)
20            for (int i = i0 + d[0], j = j0 + d[1]; 0 <= i && i < 8 && 0 <= j && j < 8; i += d[0], j += d[1]) {
21                if (board[i][j] == 'p') captures++;
22                if (board[i][j] != '.') break;  // stop if encountering a pawn or bishop
23            }
24
25        return captures;
26    }
27};

C# Solution

1
2Csharp
3public class Solution {
4    public int NumRookCaptures(char[][] board) {
5        int captures = 0;
6        int i0 = 0, j0 = 0;
7
8        // Identify the position of the Rook
9        for (int i = 0; i < 8; ++i)
10            for (int j = 0; j < 8; ++j)
11                if (board[i][j] == 'R') {
12                    i0 = i;
13                    j0 = j;
14                }
15
16        // direction vectors for north, east, south, west respectively
17        int[][] directions = {new int[]{-1, 0}, new int[]{0, 1}, new int[]{1, 0}, new int[]{0, -1}};
18        foreach (var d in directions)
19            for (int i = i0 + d[0], j = j0 + d[1]; 0 <= i && i < 8 && 0 <= j && j < 8; i += d[0], j += d[1]) {
20                if (board[i][j] == 'p') captures++;
21                if (board[i][j] != '.') break;  // stop if encountering a pawn or bishop
22            }
23
24        return captures;
25    }
26}

Each of these solutions scan the board in the four cardinal directions north, east, south, and west respectively. They start from the rook’s position and continue until a pawn is encountered (which is then captured), or a bishop or the edge of the board is reached. If a pawn is encountered while scanning in a direction, the scan in that direction is halted. The total number of captures is then returned.All solutions follow the same approach. First, they locate the rook on the board through a double for loop. Then, they use direction vectors to represent the four possible rook moves: north, east, south, and west.

After initializing a variable "captures" to 0, the algorithm iterates in each direction until it hits a friendly bishop 'B', the edge of the board, or a black pawn 'p'. If a pawn is encountered, it's captured and the number of captures increases by 1, also halting the movement in that direction.

Finally, the function or method returns the total number of captures.

It's important to note that since only a single rook and a few other pieces are presented on the 8 by 8 board, the time complexity of locating the rook and calculating the number of captures is constant, approximately O(1), since it depends on the board's fixed size, and not on the input size.

Likewise, the space complexity is O(1), as no additional space that scales with the input size is used. Only a handful of variables are used to hold the rook's position, the number of captures, and the direction vectors, therefore this also remains constant regardless of the input size.