题目描述
现有一个下标从 0 开始的 8 x 8
棋盘,上面有 3
枚棋子。
给你 6
个整数 a
、b
、c
、d
、e
和 f
,其中:
(a, b)
表示白色车的位置。(c, d)
表示白色象的位置。(e, f)
表示黑皇后的位置。
假定你只能移动白色棋子,返回捕获黑皇后所需的 最少 移动次数。
请注意:
- 车可以向垂直或水平方向移动任意数量的格子,但不能跳过其他棋子。
- 象可以沿对角线方向移动任意数量的格子,但不能跳过其他棋子。
- 如果车或象能移向皇后所在的格子,则认为它们可以捕获皇后。
- 皇后不能移动。
样例
输入:a = 1, b = 1, c = 8, d = 8, e = 2, f = 3
输出:2
解释:将白色车先移动到 (1, 3) ,然后移动到 (2, 3) 来捕获黑皇后,共需移动 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
- 两枚棋子不会同时出现在同一个格子上。
算法
(分类讨论) $O(1)$
- 注意到,车最多两步就可以捕获黑皇后,所以重点关注是否可以一步就捕获黑皇后。
- 当车与黑皇后在同一水平或竖直线上,且中间没有象的阻挡时,车可以一步捕获黑皇后。
- 当象与黑皇后在同一对角线或反对角线上,且中间没有车的阻挡时,象可以一步捕获黑皇后。
时间复杂度
- 几个条件判断,时间复杂度为常数。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int minMovesToCaptureTheQueen(int a, int b, int c, int d, int e, int f) {
if (a == e && !(a == c && min(b, f) < d && d < max(b, f)))
return 1;
if (b == f && !(b == d && min(a, e) < c && c < max(a, e)))
return 1;
if (c - d == e - f && !(a - b == c - d && min(c, e) < a && a < max(c, e)))
return 1;
if (c + d == e + f && !(a + b == c + d && min(c, e) < a && a < max(c, e)))
return 1;
return 2;
}
};