当前位置： 面试刷题>> 骑士的最短路线 (经典算法题500道)
### 题目描述补充
**题目：骑士的最短路线**
在一个无限大的国际象棋棋盘上，一个骑士（遵循国际象棋中骑士的移动规则：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 示例代码
```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 示例代码
```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 示例代码
```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;
}
```
**码小课**网站中有更多相关内容分享给大家学习，包括但不限于算法基础、数据结构、面试技巧等，欢迎大家访问学习。