Welcome to Subscribe On Youtube
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:
Input: [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
Output: 3
Explanation:
In this example the rook is able to capture all the pawns.
Example 2:
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:
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++
cppclass 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;
}
};
-
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; } } ############ class Solution { public int numRookCaptures(char[][] board) { int[] pos = find(board); int ans = 0, n = 8; int[][] dirs = new int[][] { {0, -1}, {0, 1}, {-1, 0}, {1, 0}}; for (int[] dir : dirs) { int x = pos[0], y = pos[1], a = dir[0], b = dir[1]; while ( x + a >= 0 && x + a < n && y + b >= 0 && y + b < n && board[x + a][y + b] != 'B') { x += a; y += b; if (board[x][y] == 'p') { ++ans; break; } } } return ans; } private int[] find(char[][] board) { int n = 8; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (board[i][j] == 'R') { return new int[] {i, j}; } } } return null; } } -
// OJ: https://leetcode.com/problems/available-captures-for-rook/ // Time: O(MN) // Space: O(1) class Solution { private: int dirs[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} }; int capture(vector<vector<char>>& board, int dir[2], int x, int y) { while (true) { x += dir[0]; y += dir[1]; if (x < 0 || x >= 8 || y < 0 || y >= 8 || board[x][y] == 'B') return 0; if (board[x][y] == 'p') return 1; } } public: int numRookCaptures(vector<vector<char>>& board) { int i, j, ans = 0; for (i = 0; i < 8; ++i) { for (j = 0; j < 8; ++j) { if (board[i][j] == 'R') break; } if (j < 8) break; } for (auto dir : dirs) ans += capture(board, dir, i, j); cout << i << " " << j << endl; return ans; } }; -
class Solution: def numRookCaptures(self, board: List[List[str]]) -> int: x, y, n = 0, 0, 8 for i in range(n): for j in range(n): if board[i][j] == 'R': x, y = i, j break ans = 0 for a, b in [[0, -1], [0, 1], [-1, 0], [1, 0]]: i, j = x, y while 0 <= i + a < n and 0 <= j + b < n and board[i + a][j + b] != 'B': i, j = i + a, j + b if board[i][j] == 'p': ans += 1 break return ans ############ # 999. Available Captures for Rook # https://leetcode.com/problems/available-captures-for-rook/ class Solution: def numRookCaptures(self, board: List[List[str]]) -> int: x = y = 0 for i in range(8): for j in range(8): if board[i][j] == 'R': x, y = i, j left, right = y - 1, y + 1 top, bottom = x - 1, x + 1 res = 0 while left >= 0: if board[x][left] == ".": left -= 1 elif board[x][left] == "B": break elif board[x][left] == "p": res += 1 break while right < 8: if board[x][right] == ".": right += 1 elif board[x][right] == "B": break elif board[x][right] == "p": res += 1 break while top >= 0: if board[top][y] == ".": top -= 1 elif board[top][y] == "B": break elif board[top][y] == "p": res += 1 break while bottom < 8: if board[bottom][y] == ".": bottom += 1 elif board[bottom][y] == "B": break elif board[bottom][y] == "p": res += 1 break return res -
func numRookCaptures(board [][]byte) int { n := 8 find := func() []int { for i := 0; i < n; i++ { for j := 0; j < n; j++ { if board[i][j] == 'R' { return []int{i, j} } } } return []int{} } pos := find() ans := 0 dirs := [4][2]int{ {0, -1}, {0, 1}, {1, 0}, {-1, 0} } for _, dir := range dirs { x, y, a, b := pos[0], pos[1], dir[0], dir[1] for x+a >= 0 && x+a < n && y+b >= 0 && y+b < n && board[x+a][y+b] != 'B' { x += a y += b if board[x][y] == 'p' { ans++ break } } } return ans }