[LeetCode] 每日一题 999. 可以被一步捕获的棋子数

题目链接

题目描述

给定一个 8 x 8 的棋盘，只有一个 白色的车，用字符 'R' 表示。棋盘上还可能存在白色的象 'B' 以及黑色的卒 'p'。空方块用字符 '.' 表示。

车可以按水平或竖直方向（上，下，左，右）移动任意个方格直到它遇到另一个棋子或棋盘的边界。如果它能够在一次移动中移动到棋子的方格，则能够 吃掉 棋子。

注意：车不能穿过其它棋子，比如象和卒。这意味着如果有其它棋子挡住了路径，车就不能够吃掉棋子。

返回白车将能 吃掉 的 卒的数量。

示例输入

示例 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

解释：
象阻止了车吃掉任何卒。

示例 3

输入：[[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","p",".",".",".","."],["p","p",".","R",".","p","B","."],[".",".",".",".",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."]]

输出：3

解释： 
车可以吃掉位置 b5，d6 和 f5 的卒。

提示

1. board.length == 8

2. board[i].length == 8

3. board[i][j] 可以是 'R'，'.'，'B' 或 'p'

4. 只有一个格子上存在 board[i][j] == 'R'

题解

1. 分析车的移动规则

车的移动是按水平或竖直方向进行的，并且每次移动可以跨越多个格子，直到遇到棋盘边界或者其他棋子。因此，车能够吃掉卒的位置只需要判断是否存在一个卒，并且车的路径没有被其他棋子挡住。

2. 解题步骤

1. 找到车的位置：我们首先需要遍历棋盘，找到 'R' 的位置，因为只有白车的位置才能作为移动的起点。

2. 四个方向的移动：车可以在四个方向上进行移动：

   • 向上移动

   • 向下移动

   • 向左移动

   • 向右移动

   每个方向上，车会一直向该方向移动，直到碰到边界或其他棋子。如果遇到的是卒 'p'，则白车可以吃掉该卒，并将计数器加1。如果遇到的是象 'B'，则车无法继续向该方向移动。

3. 遍历四个方向：我们依次检查四个方向，统计车可以吃掉的卒的数量。

3. 代码实现

class Solution {
    public int numRookCaptures(char[][] board) {
        // 定义四个方向：上、右、下、左
        int[][] dirs = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
        int cnt = 0;
        int x = -1, y = -1;

        // 1. 找到车的位置
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 'R') {
                    x = i;
                    y = j;
                    break;
                }
            }
            if (x != -1 && y != -1) {
                break;
            }
        }

        // 2. 在四个方向上检查车的路径
        for (int i = 0; i < 4; i++) {
            int nx = x + dirs[i][0], ny = y + dirs[i][1];
            while (nx >= 0 && nx < board.length && ny >= 0 && ny < board[0].length) {
                // 如果遇到棋子
                if (board[nx][ny] != '.') {
                    // 如果是卒 'p'，可以吃掉，计数加1
                    if (board[nx][ny] == 'p') {
                        cnt++;
                    }
                    break; // 如果遇到任何棋子（卒或象），就停止当前方向的搜索
                }
                // 向当前方向继续移动
                nx += dirs[i][0];
                ny += dirs[i][1];
            }
        }

        // 3. 返回可以吃掉的卒的数量
        return cnt;
    }
}

4. 代码解析

• dirs 数组：dirs 数组用于表示车可以移动的四个方向，每个方向由一个二元数组表示（方向的横纵坐标增量）。例如，{1, 0} 表示向下移动，{0, -1} 表示向左移动。

• 找到车的位置：我们通过双重循环遍历棋盘，找到 'R' 的坐标，并存储到 x 和 y 中。

• 遍历四个方向：对于每个方向，车会按该方向继续移动，直到遇到棋盘边界或者其他棋子。如果遇到的是卒 'p'，我们将计数器 cnt 增加1。遇到其他棋子（如象 'B'）时，车的路径被阻断，停止继续搜索该方向。

• 时间复杂度：本算法的时间复杂度为 O(1)，因为棋盘的大小固定为 8x8，最多进行 4 次方向检查，每次检查最多遍历 8 个格子，因此时间复杂度是常数级别。

总结

本题通过对车的移动路径进行模拟，采用四个方向进行遍历，在每个方向上判断车是否可以吃掉卒。通过这种方式，我们能够高效地解决问题，同时保证代码的简洁和可读性。

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。