999-可以被一步捕获的棋子数(Available Captures for Rook)
发表于：2021-12-03 | 分类： 简单
字数统计: 3.3k | 阅读时长: 15分钟 | 阅读量：

原文链接: https://leetcode-cn.com/problems/available-captures-for-rook

英文原文

On an 8 x 8 chessboard, there is exactly one white rook 'R' and some number of white bishops 'B', black pawns 'p', and empty squares '.'.

When the rook moves, it chooses one of four cardinal directions (north, east, south, or west), then moves in that direction until it chooses to stop, reaches the edge of the board, captures a black pawn, or is blocked by a white bishop. A rook is considered attacking a pawn if the rook can capture the pawn on the rook's turn. The number of available captures for the white rook is the number of pawns that the rook is attacking.

Return the number of available captures for the white rook.

 

Example 1:

Input: board = [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
Output: 3
Explanation: In this example, the rook is attacking all the pawns.

Example 2:

Input: board = [[".",".",".",".",".",".",".","."],[".","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",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
Output: 0
Explanation: The bishops are blocking the rook from attacking any of the pawns.

Example 3:

Input: board = [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","p",".",".",".","."],["p","p",".","R",".","p","B","."],[".",".",".",".",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."]]
Output: 3
Explanation: The rook is attacking the pawns at positions b5, d6, and f5.

 

Constraints:

  • board.length == 8
  • board[i].length == 8
  • board[i][j] is either 'R', '.', 'B', or 'p'
  • There is exactly one cell with board[i][j] == 'R'

中文题目

在一个 8 x 8 的棋盘上，有一个白色的车（Rook），用字符 'R' 表示。棋盘上还可能存在空方块，白色的象（Bishop）以及黑色的卒（pawn），分别用字符 '.'，'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 == board[i].length == 8
  2. board[i][j] 可以是 'R'，'.'，'B' 或 'p'
  3. 只有一个格子上存在 board[i][j] == 'R'

通过代码

高赞题解

首先，先读懂题目的意思，文字读不懂，就看示例。通过读示例，我们发现：

1、这个车子（rock）的属性很重要，它有一个「颜色」属性，并且它肯定是「白色」的；
2、这个棋盘虽然画成浅深交替出现的样子，但是棋盘没有「颜色」属性，这是一开始困扰我很久的地方（摊手）；
3、我方属性是白色的，白色的「象」（B）和我们是队友，我们只能干掉黑色属性的「卒」（p）；
4、题目说：

直到它选择停止、到达棋盘的边缘或移动到同一方格来捕获该方格上颜色相反的卒。

这里的「同一方格」和「颜色相反」我真的有很多问号。其实就是说：站在当前白色车子位置，只能朝「上下左右」四个方向横冲直撞，能消灭掉多少黑色的卒。

题目说：

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

这里的「一次移动」的一次是「上下左右」四个方向算「一次」。朝着一个方向干掉一个黑色属性的「卒」以后，就停下来，即使这个方向上还有黑色属性的「卒」都不管了，因此输出最多是 $4$。

这种问题在业界（我也不知道哪来的业界）有一个说法（不要问我咋知道的，问就是水群），就是模拟题，意即：将题目的意思直接实现出来，没有使用到特定的数据结构和方法。这些问题常常作为竞赛问题的第一个问题，也叫「签到题」，这种问题就是让你证明：

timg (4).jpeg{:width=200}
{:align=center}

为此设计算法如下：

先通过遍历棋盘，得到白车的坐标，然后对上下左右四个方向进行遍历；

  • 如果遇到 . （表示空格）就可以继续朝同一个方向前进，直到不能再走为止（到达边缘）；
  • 如果遇到 B (白色的象）就停止找（原话是：车不能与其他友方（白色）象进入同一个方格，意思就是：白色全是你的队友，我们不能误伤队友）；
  • 如果遇到 p（黑色的卒） 说明找到了，停止，计数加一。

补充：如果面试中遇到这样会让人有很多问号的问题，请大家一定要和面试官确定：你对题目中给出的条件的理解是准确无误的，具体来说有两方面：

1、避免误解题目中没有给出的条件，不要「无中生有」；

这里「敌方」和「我方」就是我假想出来的理解这个问题的东西，要和面试官确认。

2、避免题目中给出的条件被我们忽略，导致简单问题变复杂，这样其实是得不偿失的。

这里棋盘单元格的颜色深浅，是无关因素，如果考虑进去，就会增加难度，也是要和面试官确认的。

面试很多时候不会仅仅考察面试者的算法水平，有些时候，面试官只是借着面试的问题，想和面试者展开对话，这个时候我们要做的是：

1、在心态上，和面试官是平等的，我们是同事，我们一起在讨论问题，提出合理的疑问是完全没有问题的；
2、展现出积极的态度，避免暴露出消极情绪。

工作和生活中遇到的问题，很多时候就是模棱两可，边界模糊的问题。不会像是在平时练习一样，输入输出都那么明显、规范，所以有些面试官会故意把问题说得很含糊其辞，希望我们能够在和他的对话中，一起通过讨论逐渐把问题弄清楚。或者有些问题可能就是面试官在工作中遇到的问题，答案是开放的，他那里也没有标准答案。

我们和面试官的对话，在一定程度上决定了面试官是否愿意想和你成为同事。因此，合理提出疑问是我们的权利，不问就是我们的问题了。希望大家在工作中都能有积极主动搞清楚问题，并且解决问题的态度和能力。

个人观点，仅供参考。

参考代码：

[]
public class Solution {

    public int numRookCaptures(char[][] board) {
        // 因为题目已经明确给出 board.length == board[i].length == 8，所以不做输入检查
        // 定义方向数组，可以认为是四个方向向量，在棋盘问题上是常见的做法
        int[][] directions = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                
                if (board[i][j] == 'R') {
                    int res = 0;
                    for (int[] direction : directions) {
                        if (burnout(board, i, j, direction)) {
                            res++;
                        }
                    }
                    return res;
                }
            }
        }
        // 代码不会走到这里，返回 0 或者抛出异常均可
        return 0;
    }

    /**
     * burnout 横冲直撞的意思（来自欧路词典）
     *
     * @param board     输入棋盘
     * @param x         当前白象位置的横坐标
     * @param y         当前白象位置的纵坐标
     * @param direction 方向向量
     * @return 消灭一个 p，就返回 true
     */
    private boolean burnout(char[][] board, int x, int y, int[] direction) {
        int i = x;
        int j = y;
        while (inArea(i, j)) {
            // 是友军，路被堵死，直接返回
            if (board[i][j] == 'B') {
                break;
            }

            // 是敌军，拿下一血（不知道一血这个词是不是这么用的）
            if (board[i][j] == 'p') {
                return true;
            }

            i += direction[0];
            j += direction[1];
        }
        return false;
    }

    /**
     * @param i 当前位置横坐标
     * @param j 当前位置纵坐标
     * @return 是否在棋盘有效范围内
     */
    private boolean inArea(int i, int j) {
        return i >= 0 && i < 8 && j >= 0 && j < 8;
    }

    public static void main(String[] args) {
        char[][] board = {
                {'.', '.', '.', '.', '.', '.', '.', '.'},
                {'.', '.', '.', 'p', '.', '.', '.', '.'},
                {'.', '.', '.', 'R', '.', '.', '.', 'p'},
                {'.', '.', '.', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.'},
                {'.', '.', '.', 'p', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.'}};
        Solution solution = new Solution();
        int res = solution.numRookCaptures(board);
        System.out.println(res);
    }
}

复杂度分析：

  • 时间复杂度：$(N^2)$，这里 $N$ 是输入棋盘的长（宽）。找到白色车，最差情况下需要遍历完整个数组。题目固定了输入是 $8 \times 8$ 规格的棋盘，认为是 $O(1)$ 也是没有问题的。
  • 空间复杂度：$O(1)$，只使用到常数个临时变量。

统计信息

通过次数 提交次数 AC比率
30909 44744 69.1%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言
数组 矩阵 模拟
上一篇:
998-最大二叉树 II(Maximum Binary Tree II)
下一篇:
1000-合并石头的最低成本(Minimum Cost to Merge Stones)
本文目录
本文目录
    •
    本站总访问量： 次 |
    Copyright © 2020 - 2021 枫奇丶宛南 | Powered by Hexo | Theme Bamboo