题目描述补充

题目：骑士的最短路线

在一个无限大的国际象棋棋盘上，一个骑士（遵循国际象棋中骑士的移动规则：L形，即可以移动到左上方两个格子、左下方两个格子、右上方两个格子或右下方两个格子）从棋盘上的一个起始位置(startX, startY)出发，目标是到达棋盘上的另一个位置(endX, endY)。编写一个函数，计算并返回骑士从起始位置到目标位置所需的最少步数。如果无法到达目标位置，则返回-1。

示例

输入:

• startX = 2
• startY = 2
• endX = 4
• endY = 3

输出:

• 2

解释: 骑士从(2, 2)出发，可以移动到(4, 3)或(0, 3)，然后直接到达(4, 3)，因此最少需要2步。

解题思路

这个问题可以通过广度优先搜索（BFS）来解决。我们使用一个队列来存储待探索的位置，并用一个集合来记录已经访问过的位置，以避免重复搜索。我们从起始位置开始，不断将可达的、未访问过的位置加入队列，并更新步数，直到找到目标位置或队列为空。

PHP 示例代码

function knightShortestPath($startX, $startY, $endX, $endY) {
    $directions = [[-2, -1], [-2, 1], [2, -1], [2, 1], [-1, -2], [-1, 2], [1, -2], [1, 2]];
    $queue = new SplQueue();
    $queue->enqueue([$startX, $startY, 0]);
    $visited = [];
    $visited[$startX][$startY] = true;

    while (!$queue->isEmpty()) {
        [$x, $y, $steps] = $queue->dequeue();

        if ($x == $endX && $y == $endY) {
            return $steps;
        }

        foreach ($directions as $dir) {
            $nx = $x + $dir[0];
            $ny = $y + $dir[1];
            if (isset($visited[$nx][$ny])) continue;
            $visited[$nx][$ny] = true;
            $queue->enqueue([$nx, $ny, $steps + 1]);
        }
    }

    return -1; // 如果无法到达
}

Python 示例代码

from collections import deque

def knightShortestPath(startX, startY, endX, endY):
    directions = [(-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2)]
    queue = deque([(startX, startY, 0)])
    visited = set([(startX, startY)])

    while queue:
        x, y, steps = queue.popleft()

        if x == endX and y == endY:
            return steps

        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if (nx, ny) not in visited:
                visited.add((nx, ny))
                queue.append((nx, ny, steps + 1))

    return -1

JavaScript 示例代码

function knightShortestPath(startX, startY, endX, endY) {
    const directions = [[-2, -1], [-2, 1], [2, -1], [2, 1], [-1, -2], [-1, 2], [1, -2], [1, 2]];
    const queue = [[startX, startY, 0]];
    const visited = new Set([[startX, startY]]);

    while (queue.length > 0) {
        const [x, y, steps] = queue.shift();

        if (x === endX && y === endY) {
            return steps;
        }

        for (const [dx, dy] of directions) {
            const nx = x + dx;
            const ny = y + dy;
            if (!visited.has([nx, ny])) {
                visited.add([nx, ny]);
                queue.push([nx, ny, steps + 1]);
            }
        }
    }

    return -1;
}

码小课网站中有更多相关内容分享给大家学习，包括但不限于算法基础、数据结构、面试技巧等，欢迎大家访问学习。