LeetCode 999 车的可用捕获量

川长思鸟来 2022-01-22 04:13 189阅读 0赞

题目描述：

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

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

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

**示例 1：**

**![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2MjYxNDIx_size_16_color_FFFFFF_t_70][]**

![1253_example_1_improved.PNG][]

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

**示例 2：**

**![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2MjYxNDIx_size_16_color_FFFFFF_t_70 1][]**

![1253_example_2_improved.PNG][]

输入：[
    [".",".",".",".",".",".",".","."],
    [".","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：**

**![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2MjYxNDIx_size_16_color_FFFFFF_t_70 2][]**

![1253_example_3_improved.PNG][]

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

**提示：**

1.  `board.length == board[i].length == 8`
2.  `board[i][j]` 可以是 `'R'`，`'.'`，`'B'` 或 `'p'`
3.  只有一个格子上存在 `board[i][j] == 'R'`

`解题思路：`

`首先，捕获棋盘中车的位置，并且将位置记录下来。`

`然后，向东南西北四个方向搜索，将捕获到“车”的位置作为搜索的位置点，处理题目中的三种情况，`

`如果搜索到的是B“象”，直接跳出循环，`

`如果搜索到的是p“黑卒”，计数器递增，跳出循环。`

class Solution {
    public:
        int numRookCaptures(vector<vector<char>>& board) {
            int count = 0;
            //获取车的位置
            int x = -1, y = -1;
            bool flag = false;
            for(int i = 0; i < 8; i++){
                for(int j = 0; j < 8; j++){
                    if(board[i][j] == 'R'){
                        x = i;
                        y = j;
                        flag = true;
                        break;
                    }
                }
                if(flag == true) break;
            }
            
            //向东捕获
            int i = x, j = y;
            while(i < 8){
                if(board[i][j] == 'B') break;
                if(board[i][j] == 'p'){
                    count++;
                    break;
                }
                i++;
            }
            
            //向西捕获
            i = x, j = y;
            while(i >= 0){
                if(board[i][j] == 'B') break;
                if(board[i][j] == 'p'){
                    count++;
                    break;
                }
                i--;
            }
            
            //向南捕获
            i = x, j = y;
            while(j >= 0){
                if(board[i][j] == 'B') break;
                if(board[i][j] == 'p'){
                    count++;
                    break;
                }
                j--;
            }
            
            //向北捕获
            i = x, j = y;
            while(j < 8){
                if(board[i][j] == 'B') break;
                if(board[i][j] == 'p'){
                    count++;
                    break;
                }
                j++;
            }
            
            return count;
        }
    };

总结：对于棋盘类问题，首先考察的是二维数组的处理方式，然后是向东南西北四个方向的搜索问题。在经典的棋盘问题“八皇后问题”中，其中的一种方法也使用到了向四个方向的搜索。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2MjYxNDIx_size_16_color_FFFFFF_t_70]: /images/20220122/79a4a54c78bb4c00a8d5f52edb422a32.png
[1253_example_1_improved.PNG]: /images/20220122/e42961242f62415dbb020fecdd630cce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2MjYxNDIx_size_16_color_FFFFFF_t_70 1]: /images/20220122/6991fa9619ce4d5ba5b2ec10e8ebe270.png
[1253_example_2_improved.PNG]: /images/20220122/e74f87eb16d042118286985d63542c72.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2MjYxNDIx_size_16_color_FFFFFF_t_70 2]: /images/20220122/00fd1d87505845b080e5c7b39cb94c27.png
[1253_example_3_improved.PNG]: /images/20220122/c2ae50273f0e485bbdd2ab5d26714ecf.png