4061. 皇后到达目标格子的最少移动步数

难度简单

题目描述

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

给你一个数组 source = [sr, sc] 表示皇后的初始位置，以及一个数组 target = [tr, tc] 表示目标位置。

在一步移动中，皇后可以在棋盘范围内，沿着单条行、列或 对角线 移动一个或多个方格。

返回皇后移动到恰好落在 target 位置所需的最小移动次数。

示例 1：

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

输出： 1

解释：

单次对角线移动即可让皇后直接从 (8, 1) 移动到 (1, 8)。

示例 2：

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

输出： 2

解释：

皇后先从 (4, 2) 移动到 (4, 3)，然后从 (4, 3) 移动到 (1, 3)，共用 2 步移动到达目标位置。

示例 3：

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

输出： 0

解释：

皇后已经处于目标位置，因此不需要任何移动。

提示：

source == [sr, sc]
target == [tr, tc]
1 <= sr, sc, tr, tc <= 8

解法

方法一：分类讨论

思考

棋盘只有 \(8\times 8\)，从起点出发做 BFS 也能求出最短路。皇后一步可以落到同一行、同一列或同一条对角线上的任意格子，分支很多，但步数只可能是 \(0\)、 \(1\) 或 \(2\)。

起点和终点不同时，先沿行走到 \((s_r, t_c)\)，再沿列走到 \((t_r, t_c)\)。两步一定到达，而且棋盘上没有棋子阻挡。

中间格和两端重合时，起点与终点已经同行或同列，一步就能到达。因此只需判断位置是否相同，以及是否同行、同列或同对角线。

起点 \((s_r, s_c)\) 与终点 \((t_r, t_c)\) 相同时，答案是 \(0\)。

皇后一步可以沿同一行、同一列或同一条对角线移动任意格。 \(s_r=t_r\)、 \(s_c=t_c\) 或 \(|s_r-t_r|=|s_c-t_c|\) 时，一步就能落到终点，答案是 \(1\)。

其余情形分两步。先从 \((s_r, s_c)\) 走到 \((s_r, t_c)\)，再从 \((s_r, t_c)\) 走到 \((t_r, t_c)\)。此时既不同行也不同列，中间格与起点、终点都不相同。棋盘为空，所以这两步总是合法，答案是 \(2\)。

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

Python3JavaC++GoTypeScript

class Solution:
    def minQueenMoves(self, source: list[int], target: list[int]) -> int:
        sr, sc = source
        tr, tc = target
        if sr == tr and sc == tc:
            return 0
        if sr == tr or sc == tc or abs(sr - tr) == abs(sc - tc):
            return 1
        return 2

class Solution {
    public int minQueenMoves(int[] source, int[] target) {
        int sr = source[0], sc = source[1];
        int tr = target[0], tc = target[1];
        if (sr == tr && sc == tc) {
            return 0;
        }
        if (sr == tr || sc == tc || Math.abs(sr - tr) == Math.abs(sc - tc)) {
            return 1;
        }
        return 2;
    }
}

class Solution {
public:
    int minQueenMoves(vector<int>& source, vector<int>& target) {
        int sr = source[0], sc = source[1];
        int tr = target[0], tc = target[1];
        if (sr == tr && sc == tc) {
            return 0;
        }
        if (sr == tr || sc == tc || abs(sr - tr) == abs(sc - tc)) {
            return 1;
        }
        return 2;
    }
};

func minQueenMoves(source []int, target []int) int {
    sr, sc := source[0], source[1]
    tr, tc := target[0], target[1]
    if sr == tr && sc == tc {
        return 0
    }
    if sr == tr || sc == tc || abs(sr-tr) == abs(sc-tc) {
        return 1
    }
    return 2
}

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

function minQueenMoves(source: number[], target: number[]): number {
    const [sr, sc] = source;
    const [tr, tc] = target;
    if (sr === tr && sc === tc) {
        return 0;
    }
    if (sr === tr || sc === tc || Math.abs(sr - tr) === Math.abs(sc - tc)) {
        return 1;
    }
    return 2;
}

4061. 皇后到达目标格子的最少移动步数

题目描述

解法

方法一：分类讨论

评论