LeetCode.999.Available Captures for Rook 车的可用捕获量

题目描述

999 Available Captures for Rook
https://leetcode-cn.com/problems/available-captures-for-rook/

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.

在一个 8 x 8 的棋盘上，有一个白色车（rook）。也可能有空方块，白色的象（bishop）和黑色的卒（pawn）。它们分别以字符 “R”，“.”，“B” 和 “p” 给出。大写字符表示白棋，小写字符表示黑棋。

车按国际象棋中的规则移动：它选择四个基本方向中的一个（北，东，西和南），然后朝那个方向移动，直到它选择停止、到达棋盘的边缘或移动到同一方格来捕获该方格上颜色相反的卒。另外，车不能与其他友方（白色）象进入同一个方格。

返回车能够在一次移动中捕获到的卒的数量。

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’

---

解题过程

题目最后一句

返回车能够在一次移动中捕获到的卒的数量。

容易引起误解，如果只能移动一次的话，肯定做多能吃掉一个卒，但看 example 的意思是车从原点出发有多少种吃掉对方卒的方案。

时间复杂度 O(n^2)，找到车的位置需要 O(n^2)，之后上下左右走需要 O(n)
空间复杂度 O(1)

private static class SolutionV2020 {
    public int numRookCaptures(char[][] board) {
        if (null == board || 0 == board.length) {
            return 0;
        }
        int pawns = 0;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // 找到车的坐标
                if (board[i][j] == 'R') {
                    // 上
                    for (int ii = i; ii >= 0 && board[ii][j] != 'B'; ii--) {
                        if (board[ii][j] == 'p') {
                            pawns++;
                            break;
                        }
                    }
                    // 下
                    for (int ii = i; ii < board.length && board[ii][j] != 'B'; ii++) {
                        if (board[ii][j] == 'p') {
                            pawns++;
                            break;
                        }
                    }
                    // 右
                    for (int jj = j; jj < board[0].length && board[i][jj] != 'B'; jj++) {
                        if (board[i][jj] == 'p') {
                            pawns++;
                            break;
                        }
                    }
                    // 左
                    for (int jj = j; jj >= 0 && board[i][jj] != 'B'; jj--) {
                        if (board[i][jj] == 'p') {
                            pawns++;
                            break;
                        }
                    }
                }
            }
        }
        return pawns;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_999_AvailableCapturesForRook.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_999_AvailableCapturesForRook.java

---