题目描述

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

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

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

样例

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

算法1

(直接搜索) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    int numRookCaptures(vector<vector<char>>& board) {
        int x, y; // "R"的坐标
        int sum = 0;  

        for (int i = 0; i < 8; i ++) //找到'R'的位置
            for (int j = 0; j < 8; j ++)
                if (board[i][j] == 'R')
                {
                    x = i;
                    y = j;
                    break;
                }

        typedef pair <int, int> PII; //定义一个方向，这里因为只能在x，y的方向上移动，就开了一个pair数组
        PII a[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

        for (int i = 0; i < 4; i ++){
            int m = x + a[i].first, n = y + a[i].second;
            if (m >= 0 && m < 8 && n >= 0 && n < 8 && board[m][n] == 'p')
            {
                sum ++;
                continue;
            } 
            while(m >= 0 && m < 8 && n >= 0 && n < 8 && board[m][n] == '.'){
                    m += a[i].first;
                    n += a[i].second;
                    if (m >= 0 && m < 8 && n >= 0 && n < 8 && board[m][n] == 'p')
                    {
                        sum ++;
                        continue;
                    } 
                }

        }
        return sum;
    }
};