捕获黑皇后需要的最少移动次数

标签: 数组枚举

难度: Medium

现有一个下标从 1 开始的 8 x 8 棋盘，上面有 3 枚棋子。

给你 6 个整数 a 、b 、c 、d 、e 和 f ，其中：

(a, b) 表示白色车的位置。
(c, d) 表示白色象的位置。
(e, f) 表示黑皇后的位置。

假定你只能移动白色棋子，返回捕获黑皇后所需的最少移动次数。

请注意：

车可以向垂直或水平方向移动任意数量的格子，但不能跳过其他棋子。
象可以沿对角线方向移动任意数量的格子，但不能跳过其他棋子。
如果车或象能移向皇后所在的格子，则认为它们可以捕获皇后。
皇后不能移动。

示例 1：

输入：a = 1, b = 1, c = 8, d = 8, e = 2, f = 3
输出：2
解释：将白色车先移动到 (1, 3) ，然后移动到 (2, 3) 来捕获黑皇后，共需移动 2 次。
由于起始时没有任何棋子正在攻击黑皇后，要想捕获黑皇后，移动次数不可能少于 2 次。

示例 2：

输入：a = 5, b = 3, c = 3, d = 4, e = 5, f = 2
输出：1
解释：可以通过以下任一方式移动 1 次捕获黑皇后：
- 将白色车移动到 (5, 2) 。
- 将白色象移动到 (5, 2) 。

提示：

1 <= a, b, c, d, e, f <= 8
两枚棋子不会同时出现在同一个格子上。

Submission

运行时间: 20 ms

内存: 0.0 MB

class Solution:
    def minMovesToCaptureTheQueen(self, a: int, b: int, c: int, d: int, e: int, f: int) -> int:
        if a == e:
            return 2 if a == c and (b < d < f or b > d > f) else 1
        if b == f:
            return 2 if b == d and (a < c < e or a > c > e) else 1
        if c+d == e+f:
            return 2 if a+b == c+d and (c < a < e or c > a > e) else 1
        if c-d == e-f:
            return 2 if a-b == c-d and (c < a < e or c > a > e) else 1
        return 2

Explain

此题解的核心思路是利用棋子的移动规则直接判断白车和白象能否直接或间接捕获黑皇后。首先检查白车是否在与黑皇后同一行或同一列上，如果是则可以直接捕获，除非白象阻挡在中间需要先移动白象。其次检查白象是否在与黑皇后同一对角线上，如果是则也可以直接捕获，除非白车阻挡在中间需要先移动白车。如果以上情况都不满足，说明至少需要两步才能捕获黑皇后。

时间复杂度: O(1)

空间复杂度: O(1)

class Solution:
    def minMovesToCaptureTheQueen(self, a: int, b: int, c: int, d: int, e: int, f: int) -> int:
        # 检查白车是否与黑皇后同一行
        if a == e:
            # 若白象也在该行且位于白车与黑皇后之间，则需要两步
            return 2 if a == c and (b < d < f or b > d > f) else 1
        # 检查白车是否与黑皇后同一列
        if b == f:
            # 若白象也在该列且位于白车与黑皇后之间，则需要两步
            return 2 if b == d and (a < c < e or a > c > e) else 1
        # 检查白象是否与黑皇后同一正对角线
        if c+d == e+f:
            # 若白车也在该对角线且位于白象与黑皇后之间，则需要两步
            return 2 if a+b == c+d and (c < a < e or c > a > e) else 1
        # 检查白象是否与黑皇后同一负对角线
        if c-d == e-f:
            # 若白车也在该对角线且位于白象与黑皇后之间，则需要两步
            return 2 if a-b == c-d and (c < a < e or c > a > e) else 1
        # 如果以上条件都不满足，则至少需要两步
        return 2

Explore

算法基于题目设定，假设棋盘上仅有三个棋子：白车、白象和黑皇后。因此，除了这三个棋子之外，没有其他棋子存在于棋盘上。这样的假设简化了问题，使得算法只需考虑这三个棋子的相对位置和移动规则。

题解中并未详细描述当白车和白象都无法直接捕获黑皇后时的具体移动策略，只是简单地返回了'至少需要两步'。在实际应用中，这种情况下的最佳策略可能涉及将一方棋子移动到可捕获位置，同时避免阻挡另一方棋子的捕获路径，或者优先考虑最快能达到捕获位置的棋子。具体策略需要根据棋子的初始位置和目标位置进一步分析确定。

根据题解中的代码实现，如果白车与黑皇后在同一行或同一列，且白象不位于它们之间，则白车可以直接捕获黑皇后，返回1步即可。同样，如果白象与黑皇后在同一对角线上，且白车不位于它们之间，则白象也可以直接捕获黑皇后，同样返回1步。因此，算法只在棋子位置相互阻挡时才会返回需要两步。