时间戳

首页 > 技术文章 > 999. 车的可用捕获量

999. 车的可用捕获量

hencins 2020-03-27 10:01 原文

999. 车的可用捕获量

题目

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

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

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

示例 1：

1

输入：

[
    [".",".",".",".",".",".",".","."],
    [".",".",".","p",".",".",".","."],
    [".",".",".","R",".",".",".","p"],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".","p",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."]
]

输出：3
解释：在本例中，车能够捕获所有的卒。

示例 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
解释：象阻止了车捕获任何卒。

提示：

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

解题

  1. 四种元素，R(车)，B（象），p（卒），.(空)
  2. 数量，车1个，其他大于等于0个
  3. 在车的竖直或水平方向上，对没被象挡住的卒进行求和

建立8x8矩阵，定位R坐标，扫描R的纵轴和横轴，返回可以直接进行R-p的坐标的数量

class Solution {
public:
    int numRookCaptures(vector<vector<char>>& board) {
        int R_i, R_j;
        int count = 0;
        for (int i = 0; i < 8; ++i) {
            for (int j = 0; j < 8; ++j) {
                if (board[i][j] == 'R') {
                    R_i = i;
                    R_j = j;
                    i = 8; // 直接跳出
                    break;
                }
            }
        }
        // 提取R_i行和R_j列
        for (int i = R_i - 1; i > -1; --i) {
            if (board[i][R_j] == 'p') {
                count++;
                break;
            } else if (board[i][R_j] == '.') {
                continue;
            } else {
                break;
            }
        }
        for (int i = R_i + 1; i < 8; ++i) {
            if (board[i][R_j] == 'p') {
                count++;
                break;
            } else if (board[i][R_j] == '.') {
                continue;
            } else {
                break;
            }
        }
        for (int j = R_j - 1; j > -1; --j) {
            if (board[R_i][j] == 'p') {
                count++;
                break;
            } else if (board[R_i][j] == '.') {
                continue;
            } else {
                break;
            }
        }
        for (int j = R_j + 1; j < 8; ++j) {
            if (board[R_i][j] == 'p') {
                count++;
                break;
            } else if (board[R_i][j] == '.') {
                continue;
            } else {
                break;
            }
        }
        return count;
    }
};

测试代码：

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int numRookCaptures(vector<vector<char>>& board) {
        int R_i, R_j;
        int count = 0;
        for (int i = 0; i < 8; ++i) {
            for (int j = 0; j < 8; ++j) {
                if (board[i][j] == 'R') {
                    R_i = i;
                    R_j = j;
                    i = 8; // 直接跳出
                    break;
                }
            }
        }
        // 提取R_i行和R_j列
        for (int i = R_i - 1; i > -1; --i) {
            if (board[i][R_j] == 'p') {
                count++;
            } else if (board[i][R_j] == '.') {
                continue;
            } else {
                break;
            }
        }
        for (int i = R_i + 1; i < 8; ++i) {
            if (board[i][R_j] == 'p') {
                count++;
            } else if (board[i][R_j] == '.') {
                continue;
            } else {
                break;
            }
        }
        for (int j = R_j - 1; j > -1; --j) {
            if (board[R_i][j] == 'p') {
                count++;
            } else if (board[R_i][j] == '.') {
                continue;
            } else {
                break;
            }
        }
        for (int j = R_j + 1; j < 8; ++j) {
            if (board[R_i][j] == 'p') {
                count++;
            } else if (board[R_i][j] == '.') {
                continue;
            } else {
                break;
            }
        }
        return count;
    }
};

int main() {
    vector<vector<char>> board = 
        {
            {'.','.','.','.','.','.','.','.'},
            {'.','.','.','p','.','.','.','.'},
            {'.','.','.','p','.','.','.','.'},
            {'p','p','.','R','.','p','B','.'},
            {'.','.','.','.','.','.','.','.'},
            {'.','.','.','B','.','.','.','.'},
            {'.','.','.','p','.','.','.','.'},
            {'.','.','.','.','.','.','.','.'}
        };

    Solution b;
    printf("%d\n", b.numRookCaptures(board));

    return 0;
}

优解

class Solution {
public:
    int numRookCaptures(vector<vector<char>>& board) {
        int cnt = 0, st = 0, ed = 0;
        int dx[4] = {0, 1, 0, -1}; // x轴和y轴的方向数组控制
        int dy[4] = {1, 0, -1, 0};
        for (int i = 0; i < 8; ++i) {
            for (int j = 0; j < 8; ++j) {
                if (board[i][j] == 'R') {
                    st = i;
                    ed = j;  // 我觉得可以像我一样增加一个改i值跳出嵌套循环
                    break;
                }
            }
        }
        // 圈扩散
        for (int i = 0; i < 4; ++i) {
            for (int step = 0;; ++step) {
                int tx = st + step * dx[i];
                int ty = ed + step * dy[i];
                if (tx < 0 || tx >= 8 || ty < 0 || ty >= 8 || board[tx][ty] == 'B') break;
                if (board[tx][ty] == 'p') {
                    cnt++;
                    break;
                }
            }
        }
        return cnt;
    }
}

推荐阅读