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：

输入：a = 5, b = 3, c = 3, d = 4, e = 5, f = 2
输出：1
解释：我们可以通过一步捕获黑皇后：
- 将白车移动到 (5, 2)
- 将白象移动到 (5, 2)

约束条件：

  • 1 <= a, b, c, d, e, f <= 8
  • 没有两个棋子在同一格子上

提示：

  • 最少移动次数只能是 1 或 2
  • 如果皇后在车或象的攻击路径上且中间没有阻挡，答案就是 1

解题思路

解题思路

根据题目提示，答案只能是 1 或 2，所以我们只需要判断是否能在一步内捕获皇后。

一步捕获的条件：

  1. 车能一步捕获皇后：车和皇后在同一行或同一列，且中间没有象阻挡
  2. 象能一步捕获皇后：车和皇后在同一对角线上，且中间没有车阻挡

具体分析：

  • 车的攻击范围：同行（a == e）或同列（b == f）

    • 如果车和皇后同行，需要检查象是否在它们之间阻挡
    • 如果车和皇后同列，需要检查象是否在它们之间阻挡

  • 象的攻击范围：对角线（|c-e| == |d-f|）

    • 如果象和皇后在同一对角线，需要检查车是否在它们之间阻挡

  • 阻挡判断：如果阻挡棋子在攻击路径的中间位置，就构成阻挡

如果两个棋子都不能一步捕获皇后，那么答案就是 2（总是可以在两步内完成）。

代码实现

class Solution {
public:
    int minMovesToCaptureTheQueen(int a, int b, int c, int d, int e, int f) {
        // 检查车是否能一步捕获皇后
        // 同行
        if (a == e) {
            // 检查象是否在车和皇后之间阻挡
            if (c == a && ((d > min(b, f) && d < max(b, f)))) {
                // 象在中间，车不能直接捕获
            } else {
                return 1;
            }
        }
        // 同列
        if (b == f) {
            // 检查象是否在车和皇后之间阻挡
            if (d == b && ((c > min(a, e) && c < max(a, e)))) {
                // 象在中间，车不能直接捕获
            } else {
                return 1;
            }
        }
        
        // 检查象是否能一步捕获皇后
        // 同对角线
        if (abs(c - e) == abs(d - f)) {
            // 检查车是否在象和皇后之间阻挡
            // 计算车到对角线的距离
            int dx = e - c;
            int dy = f - d;
            if (dx != 0) {
                // 检查车是否在对角线上
                int steps = (a - c) * dy - (b - d) * dx;
                if (steps == 0) {
                    // 车在对角线上，检查是否在中间
                    if ((a > min(c, e) && a < max(c, e)) && 
                        (b > min(d, f) && b < max(d, f))) {
                        // 车在中间，象不能直接捕获
                    } else {
                        return 1;
                    }
                } else {
                    return 1;
                }
            }
        }
        
        return 2;
    }
};

class Solution:
    def minMovesToCaptureTheQueen(self, a: int, b: int, c: int, d: int, e: int, f: int) -> int:
        # 检查车是否能一步捕获皇后
        # 同行
        if a == e:
            # 检查象是否在车和皇后之间阻挡
            if c == a and min(b, f) < d < max(b, f):
                pass  # 象在中间，车不能直接捕获
            else:
                return 1
        
        # 同列
        if b == f:
            # 检查象是否在车和皇后之间阻挡
            if d == b and min(a, e) < c < max(a, e):
                pass  # 象在中间，车不能直接捕获
            else:
                return 1
        
        # 检查象是否能一步捕获皇后
        # 同对角线
        if abs(c - e) == abs(d - f):
            # 检查车是否在象和皇后之间阻挡
            dx = 1 if e > c else -1
            dy = 1 if f > d else -1
            
            # 检查车是否在对角线上且在中间
            blocked = False
            x, y = c + dx, d + dy
            while x != e or y != f:
                if x == a and y == b:
                    blocked = True
                    break
                x += dx
                y += dy
            
            if not blocked:
                return 1
        
        return 2

public class Solution {
    public int MinMovesToCaptureTheQueen(int a, int b, int c, int d, int e, int f) {
        // 检查车是否能一步捕获皇后
        // 同行
        if (a == e) {
            // 检查象是否在车和皇后之间阻挡
            if (c == a && d > Math.Min(b, f) && d < Math.Max(b, f)) {
                // 象在中间，车不能直接捕获
            } else {
                return 1;
            }
        }
        
        // 同列
        if (b == f) {
            // 检查象是否在车和皇后之间阻挡
            if (d == b && c > Math.Min(a, e) && c < Math.Max(a, e)) {
                // 象在中间，车不能直接捕获
            } else {
                return 1;
            }
        }
        
        // 检查象是否能一步捕获皇后
        // 同对角线
        if (Math.Abs(c - e) == Math.Abs(d - f)) {
            // 检查车是否在象和皇后之间阻挡
            int dx = e > c ? 1 : -1;
            int dy = f > d ? 1 : -1;
            
            bool blocked = false;
            int x = c + dx, y = d + dy;
            while (x != e || y != f) {
                if (x == a && y == b) {
                    blocked = true;
                    break;
                }
                x += dx;
                y += dy;
            }
            
            if (!blocked) {
                return 1;
            }
        }
        
        return 2;
    }
}

var minMovesToCaptureTheQueen = function(a, b, c, d, e, f) {
    // Check if rook can capture queen in 1 move
    if (a === e || b === f) {
        // Same row or column, check if bishop blocks
        if (a === e) {
            // Same row
            if (c === a && ((d > Math.min(b, f) && d < Math.max(b, f)))) {
                // Bishop blocks
            } else {
                return 1;
            }
        } else {
            // Same column
            if (d === b && ((c > Math.min(a, e) && c < Math.max(a, e)))) {
                // Bishop blocks
            } else {
                return 1;
            }
        }
    }
    
    // Check if bishop can capture queen in 1 move
    if (Math.abs(c - e) === Math.abs(d - f)) {
        // On same diagonal, check if rook blocks
        let dx = e > c ? 1 : -1;
        let dy = f > d ? 1 : -1;
        let blocked = false;
        
        for (let x = c + dx, y = d + dy; x !== e; x += dx, y += dy) {
            if (x === a && y === b) {
                blocked = true;
                break;
            }
        }
        
        if (!blocked) {
            return 1;
        }
    }
    
    return 2;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(1)
空间复杂度O(1)

时间复杂度：O(1) - 由于棋盘大小固定为8x8，所有的判断和循环都是常数时间 空间复杂度：O(1) - 只使用了常数个变量存储坐标和状态

相关题目