跳转至

3996. 偶数次骑士移动

题目描述

给你两个整数数组 start 和 target，每个数组的形式均为 [x, y]，表示标准 8 x 8 国际象棋棋盘上的一个格子。

如果骑士可以用 偶数 次移动从 start 到达 target，则返回 true；否则返回 false。

注意：骑士的一次合法移动是：沿一个方向移动两格，再沿与其垂直的方向移动一格。下图展示了骑士从一个格子出发时所有 8 种可能的移动方式。

 

示例 1：

输入： start = [1,1], target = [2,2]

输出： true

解释：

一种可行的移动序列为 (1, 1) -> (3, 2) -> (2, 4) -> (4, 3) -> (2, 2)。

骑士经过 4 次移动到达目标位置，4 是偶数。因此答案为 true。

示例 2：

输入： start = [4,5], target = [6,6]

输出： false

解释：

骑士无法用偶数次移动从 start = [4, 5] 到达 target = [6, 6]。因此答案为 false。

 

提示：

  • start.length == target.length == 2
  • 0 <= start[i], target[i] <= 7

解法

方法一：奇偶性

骑士每次移动的偏移量为 \((\pm 1, \pm 2)\) 或 \((\pm 2, \pm 1)\)，因此坐标和 \(x + y\) 的变化量恒为奇数，即每次移动都会改变格子颜色（以 \((x + y) \bmod 2\) 区分黑白格）。

由此可得：

  • 偶数次移动后，起点与终点颜色相同；
  • 奇数次移动后，起点与终点颜色不同。

在 \(8 \times 8\) 棋盘上，骑士可以到达任意格子，且到达同色格子的任意路径长度必为偶数。因此，只需判断起点与终点的 \((x + y) \bmod 2\) 是否相等即可。

时间复杂度 \(O(1)\)，空间复杂度 \(O(1)\)。

1
2
3
class Solution:
    def canReach(self, start: list[int], target: list[int]) -> bool:
        return (start[0] + start[1]) % 2 == (target[0] + target[1]) % 2

1
2
3
4
5
class Solution {
    public boolean canReach(int[] start, int[] target) {
        return (start[0] + start[1]) % 2 == (target[0] + target[1]) % 2;
    }
}

1
2
3
4
5
6
class Solution {
public:
    bool canReach(vector<int>& start, vector<int>& target) {
        return (start[0] + start[1]) % 2 == (target[0] + target[1]) % 2;
    }
};

1
2
3
func canReach(start []int, target []int) bool {
    return (start[0]+start[1])%2 == (target[0]+target[1])%2
}

1
2
3
function canReach(start: number[], target: number[]): boolean {
    return (start[0] + start[1]) % 2 === (target[0] + target[1]) % 2;
}

评论