跳转至

4034. 象到达目标格子的最少移动步数

题目描述

给你一个 8 x 8 的棋盘，行和列的下标从 1 开始。

给你一个数组 source = [sr, sc]，表示 象 的起始位置，以及一个数组 target = [tr, tc]。在一步移动中，象可以在棋盘范围内沿着单个 对角线 方向移动任意数量的格子。

返回象 恰好 到达 target 位置所需的 最少 移动次数。如果它永远无法到达 target，则返回 -1。

 

示例 1：

输入： source = [8,1], target = [1,8]

输出： 1

解释：

一步对角线移动即可将象直接从 (8, 1) 送达 (1, 8)。

示例 2：

输入： source = [4,2], target = [1,3]

输出： 2

解释：

象从 (4, 2) 移动到 (3, 1)，然后再从 (3, 1) 移动到 (1, 3)，经过 2 步移动到达目标位置。

示例 3：

输入： source = [1,1], target = [3,4]

输出： -1

解释：

无论进行多少次对角线移动，从 (1, 1) 出发的象都永远无法到达 (3, 4)。因此，答案是 -1。

 

提示：

  • source.length == target.length == 2
  • 1 <= sr, sc, tr, tc <= 8
  • source != target

解法

方法一：分类讨论

象每次只能沿着对角线移动，一次移动会使行、列同时增减相同的数量，因此 \((r + c) \bmod 2\) 始终保持不变，即象只能停留在与起点同色的格子上。若 \((sr + sc)\) 与 \((tr + tc)\) 奇偶性不同，象永远无法到达目标，返回 \(-1\)。

否则，若起点与终点位于同一条对角线上，即 \(|sr - tr| = |sc - tc|\)，那么一步即可到达，返回 \(1\)。

其余情况下，两个格子同色但不共线，题目保证 \(\textit{source} \neq \textit{target}\)，而 \(8 \times 8\) 棋盘上任意两个同色格子之间都存在一个可以中转的格子，因此答案为 \(2\)。

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

1
2
3
4
5
6
7
8
9
class Solution:
    def minBishopMoves(self, source: List[int], target: List[int]) -> int:
        sr, sc = source
        tr, tc = target
        if (sr + sc) % 2 != (tr + tc) % 2:
            return -1
        if abs(sr - tr) == abs(sc - tc):
            return 1
        return 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int minBishopMoves(int[] source, int[] target) {
        int sr = source[0], sc = source[1];
        int tr = target[0], tc = target[1];
        if ((sr + sc) % 2 != (tr + tc) % 2) {
            return -1;
        }
        if (Math.abs(sr - tr) == Math.abs(sc - tc)) {
            return 1;
        }
        return 2;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int minBishopMoves(vector<int>& source, vector<int>& target) {
        int sr = source[0], sc = source[1];
        int tr = target[0], tc = target[1];
        if ((sr + sc) % 2 != (tr + tc) % 2) {
            return -1;
        }
        if (abs(sr - tr) == abs(sc - tc)) {
            return 1;
        }
        return 2;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func minBishopMoves(source []int, target []int) int {
    sr, sc := source[0], source[1]
    tr, tc := target[0], target[1]
    if (sr+sc)%2 != (tr+tc)%2 {
        return -1
    }
    if abs(sr-tr) == abs(sc-tc) {
        return 1
    }
    return 2
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function minBishopMoves(source: number[], target: number[]): number {
    const [sr, sc] = source;
    const [tr, tc] = target;
    if ((sr + sc) % 2 !== (tr + tc) % 2) {
        return -1;
    }
    if (Math.abs(sr - tr) === Math.abs(sc - tc)) {
        return 1;
    }
    return 2;
}

评论