Available Captures For Rook - Leetcode Solution

Problem Statement:

On an 8x8 chessboard, there is one white rook. There also may be empty squares, white bishops, and black pawns. These are given as characters 'R', '.', 'B', and 'p' respectively. Uppercase characters represent white pieces, and lowercase characters represent black pieces.

The rook moves as in the rules of Chess: it chooses one of four cardinal directions (north, east, west, and south), then moves in that direction until it chooses to stop, reaches the edge of the board, or captures an opposite colored pawn by moving to the same square it occupies. Also, rooks cannot move over other pieces.

Return the number of pawns the rook can capture in one move.

Example 1:

Input: [[".",".",".",".",".",".",".","."], [".",".",".","p",".",".",".","."], [".",".",".","R",".",".",".","B"], [".",".",".",".",".",".",".","."], [".",".",".",".",".",".",".","."], [".",".",".","B",".",".",".","."], [".",".",".",".",".",".",".","."], [".",".",".",".",".",".",".","."]] Output: 3 Explanation: In this example, the rook is located at (2,3) on the board. It can capture the pawn at (1,3) with the move "Rb3". It can capture the pawn at (2,2) with the move "Rc3". And it can capture the pawn at (4,3) with the move "Rf3". So the output is 3.

Approach:

We need to find the number of pawns the given rook can capture in one move. Initially, we need to find the position of the rook on the chessboard. Once we have the position, we can traverse its row and column simultaneously to find out all the available captures for the rook.

We need to create four flags to capture all four directions available for the rook. We can assign 1 to the flag for the direction in which the rook is moving, otherwise, 0.

We can loop through all the cells of the rook's row and column simultaneously. If we encounter any bishop before finding any pawn, then the rook cannot capture any pawn in that row or column. However, if we encounter any pawn before finding any bishop, then we can increase the number of available captures by 1 and break the loop.

We need to return the count of all such pawns in the row and the column.

Algorithm:

1. Find the position of the rook in the given chessboard.
2. Initialize all the flags for the four directions to 0.
3. Loop through the row and the column of the rook position until we find any bishop or pawn.
4. If we encounter any bishop, then break the loop.
5. If we encounter any pawn, then increase the count of available captures by 1 and break the loop.
6. Return the count.

Code:

Time Complexity: O(8+N), where N is the total count of cells in the row and column of the rook's position. Space Complexity: O(1), as we are not using any extra data structure to solve this problem.

Solution:

class Solution { public: int numRookCaptures(vector<vector<char>>& board) { int r, c; for(int i = 0; i < 8; i++) { for(int j = 0; j < 8; j++) { if(board[i][j] == 'R') { r = i; c = j; break; } } } int count = 0, flagE = 0, flagW = 0, flagN = 0, flagS = 0; for(int i = r + 1; i < 8; i++) { if(board[i][c] == 'p') { count++; break; } else if(board[i][c] == 'B') { break; } } for(int i = r - 1; i >= 0; i--) { if(board[i][c] == 'p') { count++; break; } else if(board[i][c] == 'B') { break; } } for(int i = c + 1; i < 8; i++) { if(board[r][i] == 'p') { count++; break; } else if(board[r][i] == 'B') { break; } } for(int i = c - 1; i >= 0; i--) { if(board[r][i] == 'p') { count++; break; } else if(board[r][i] == 'B') { break; } } return count; } };

1