车的可用捕获量

题目

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

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

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

示例 1：

示例1

输入：[[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
输出：3
解释：
在本例中，车能够捕获所有的卒。

示例 2：

示例2

输入：[[".",".",".",".",".",".",".","."],[".","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",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
输出：0
解释：
象阻止了车捕获任何卒。

示例3

示例3

输入：[[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","p",".",".",".","."],["p","p",".","R",".","p","B","."],[".",".",".",".",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."]]
输出：3
解释：
车可以捕获位置 b5，d6 和 f5 的卒。

解题思路

本体最难还是在于理解题意，感觉为了出一道算法题，得先学会好多东西。
总共分两步，一，找到车的位置，二，找到车走一次（上下左右）后的结果。

1. n^2时间复杂度找到车的坐标位置（x，y）。
2. 以该坐标为原点，分别从左右上下，找到所有符合的子结果。复杂度4n。
3. 判断条件为，遇到‘B’那么结束当前方向的寻找，遇到‘p’总结果+1，并结束当前方向的寻找。
4. 返回最终结果。时间复杂度O(n^2).

代码

class Solution {
    public int numRookCaptures(char[][] board) {
        // 先找到车
        // 上下左右找
        // 遇到象时停止
        // 遇到p时值++，并停止
        // 返回结果
        int x = 0,y = 0;
        for (int i = 0; i < board.length; i++){
            for (int j = 0; j < board[i].length; j++){
                char str = board[i][j];
                if (str == 'R'){
                    x = i;
                    y = j;
                    break;
                }
            }
        }   

        int res = 0;
        //向左
        for (int i = x; i > 0; i--){
            char str = board[i][y];
            if (str == 'B'){
                break;
            }else if (str == 'p'){
                res ++;
                break;
            }
        }
        // 向右
        for (int i = x; i < board.length; i++){
            char str = board[i][y];
            if (str == 'B'){
                break;
            }else if (str == 'p'){
                res ++;
                break;
            }
        }

        // 向上
        for (int j = y; j < board[x].length; j++){
            char str = board[x][j];
            if (str == 'B'){
                break;
            }else if (str == 'p'){
                res ++;
                break;
            }
        }

        // 向下

        for (int j = y; j > 0; j--){
            char str = board[x][j];
            if (str == 'B'){
                break;
            }else if (str == 'p'){
                res ++;
                break;
            }
        }

        return res;
    }
}