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

· 2024-12-5   · 次阅读   · 字数统计: 274字   · 阅读时长≈ 1分钟

  · 算法题解   · LeetCode

题目链接

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

分析

分类讨论即可

如果车或者象可以直接攻击到皇后，答案为 $1$

如果象可以攻击到皇后，但被车挡住，移开车即可，答案为 $2$

如果车可以攻击到皇后，但被象挡住，同上

对于其他情况，移动两次车即可，答案为 $2$

代码实现

class Solution {
public:
    int minMovesToCaptureTheQueen(int a, int b, int c, int d, int e, int f) {
        auto checkMid = [](int x, int y, int z) -> bool 
        {
            return min(x, z) < y && y < max(x, z);
        };

        // 判断车是否可以直接攻击到皇后
        if(a == e && (a != c || !checkMid(b, d, f)) || b == f && (b != d || !checkMid(a, c, e)))
            return 1;
  
        // 判断主教是否可以直接攻击到皇后
        if(c + d == e + f && (a + b != c + d || !checkMid(c, a, e)) || c - d == e - f && (a - b != c - d || !checkMid(c, a, e)))
            return 1;
  
        // 否则车移动两次一定可以攻击到皇后
        return 2;
    }
};

复杂度分析

  • 时间复杂度：$O(1)$
  • 空间复杂度：$O(1)$