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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.