Question

Formatted question description: https://leetcode.ca/all/999.html

On an 8 x 8 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 into the same square as other friendly bishops.

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

Example 1:

image

Input: [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
Output: 3
Explanation:
In this example the rook is able to capture all the pawns.
Example 2:

image

Input: [[".",".",".",".",".",".",".","."],[".","p","p","p","p","p",".","."],[".","p","p","B","p","p",".","."],[".","p","B","R","B","p",".","."],[".","p","p","B","p","p",".","."],[".","p","p","p","p","p",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
Output: 0
Explanation:
Bishops are blocking the rook to capture any pawn.
Example 3:

image

Input: [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","p",".",".",".","."],["p","p",".","R",".","p","B","."],[".",".",".",".",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."]]
Output: 3
Explanation:
The rook can capture the pawns at positions b5, d6 and f5.
Note:

board.length == board[i].length == 8
board[i][j] is either 'R', '.', 'B', or 'p'
There is exactly one cell with board[i][j] == 'R'

Algorithm 1

In chess, the rook can go up, down, left, and right. If you encounter White’s bishop on a certain path, you can’t eat pawns on that road. If you encounter pawns first, you can eat them. There are soldiers, which cannot be eaten continuously. It’s actually very simple to understand the meaning of the question.

First, traverse the chessboard to find the position of the white rook. Then the simplest and rude way is to traverse the four directions with a for loop. If you encounter White’s bishop, break directly. If a pawn is encountered, the result res is incremented by 1, and then break can be done, see the code as follows:

Code 1

C++

class Solution {
public:
    int numRookCaptures(vector<vector<char>>& board) {
		int x = 0, y = 0, res = 0;
		for (int i = 0; i < 8; ++i) {
			for (int j = 0; j < 8; ++j) {
				if (board[i][j] == 'R') {
					x = i; y = j; break;
				}
			}
		}
		for (int j = y; j >= 0; --j) {
			if (board[x][j] == 'B') break;
			if (board[x][j] == 'p') {++res; break;} 
		}
		for (int j = y; j < 8; ++j) {
			if (board[x][j] == 'B') break;
			if (board[x][j] == 'p') {++res; break;}  
		}
		for (int i = x; i >= 0; --i) {
			if (board[i][y] == 'B') break;
			if (board[i][y] == 'p') {++res; break;} 
		}
		for (int i = x; i < 8; ++i) {
			if (board[i][y] == 'B') break;
			if (board[i][y] == 'p') {++res; break;} 
		}
		return res;
    }
};

Algorithm 2

We can also not write such a for loop, but use the idea of depth-first traversal of DFS, use the direction array, add the offset of the direction each time, if there is no cross-boundary, then judge, if it is a black soldier, the result res is increased by 1. If it is not a point, then break. This judgment is very essential. It covers the current situation of a white elephant or a black soldier, ensuring that you can break after encountering a white elephant or having eaten a black soldier, and then continue to increase the offset until you exit the loop. See the code as follows:

Code 2

C++

class Solution {
public:
    int numRookCaptures(vector<vector<char>>& board) {
        int x0 = 0, y0 = 0, res = 0;
        vector<vector<int>> dirs{ {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
		for (int i = 0; i < 8; ++i) {
			for (int j = 0; j < 8; ++j) {
				if (board[i][j] == 'R') {
					x0 = i; y0 = j; break;
				}
			}
		}
        for (auto &dir : dirs) {
            int x = x0 + dir[0], y = y0 + dir[1];
            while (x >= 0 && x < 8 && y >= 0 && y < 8) {
                if (board[x][y] == 'p') ++res;
                if (board[x][y] != '.') break;
                x += dir[0]; y += dir[1];
            }
        }
        return res;
    }
};

Java

class Solution {
    public int numRookCaptures(char[][] board) {
        int rookRow = -1, rookColumn = -1;
        int rows = board.length, columns = board[0].length;
        int totalSquares = rows * columns;
        for (int i = 0; i < totalSquares; i++) {
            int row = i / columns, column = i % columns;
            if (board[row][column] == 'R') {
                rookRow = row;
                rookColumn = column;
                break;
            }
        }
        if (rookRow < 0 || rookColumn < 0)
            return 0;
        int count = 0;
        int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
        for (int[] direction : directions) {
            int tempRow = rookRow + direction[0], tempColumn = rookColumn + direction[1];
            while (tempRow >= 0 && tempRow < rows && tempColumn >= 0 && tempColumn < columns) {
                if (board[tempRow][tempColumn] != '.') {
                    if (board[tempRow][tempColumn] == 'p')
                        count++;
                    break;
                }
                tempRow += direction[0];
                tempColumn += direction[1];
            }
        }
        return count;
    }
}

All Problems

All Solutions