当前位置： 面试刷题>> 地图跳跃 (经典算法题500道)
### 题目描述补充
**地图跳跃**
在一个由`n`个节点组成的地图中，每个节点都有一个唯一的编号从`0`到`n-1`。地图中的某些节点对之间存在直接连接的边，形成一个无向图。现在，你位于起始节点`start`，目标是要通过一系列跳跃（即沿着边移动到相邻的节点）到达目标节点`end`。跳跃过程中，你每次可以跳跃的最大距离由`maxJump`给出，即你可以从当前节点跳到任何与其编号差不超过`maxJump`的节点（包括自身，如果`maxJump`允许的话）。
你需要编写一个函数来判断从起始节点`start`是否可以通过一系列的跳跃到达目标节点`end`。
### 示例
**输入**:
- 图的表示方式：可以使用邻接表、邻接矩阵或其他方式，这里以邻接表为例。
- `graph`: `[[1, 3], [0, 2], [0, 1, 3], [3]]` 表示节点0连接到节点1和3，节点1连接到节点0和2，节点2连接到节点0、1和3，节点3连接到节点2。
- `start`: 0
- `end`: 3
- `maxJump`: 2
**输出**:
- `true` （因为可以从节点0跳到节点1或3，然后再跳到节点3）
### PHP 示例代码
```php
function canReachDestination($graph, $start, $end, $maxJump) {
$n = count($graph);
$visited = array_fill(0, $n, false); // 记录节点是否已访问
// 深度优先搜索函数
function dfs($node, $target, $maxJump, $visited, $graph) {
if ($node == $target) return true; // 达到目标
$visited[$node] = true; // 标记为已访问
for ($i = max(0, $node - $maxJump); $i <= min($n - 1, $node + $maxJump); $i++) {
if (isset($graph[$node][$i]) && !$visited[$i]) {
if (dfs($i, $target, $maxJump, $visited, $graph)) {
return true;
}
}
}
return false;
}
return dfs($start, $end, $maxJump, $visited, $graph);
}
// 示例用法
$graph = [[1, 3], [0, 2], [0, 1, 3], [3]];
$start = 0;
$end = 3;
$maxJump = 2;
echo canReachDestination($graph, $start, $end, $maxJump) ? "true" : "false";
```
### Python 示例代码
```python
def canReachDestination(graph, start, end, maxJump):
n = len(graph)
visited = [False] * n
def dfs(node):
if node == end:
return True
visited[node] = True
for neighbor in range(max(0, node - maxJump), min(n, node + maxJump) + 1):
if neighbor in graph[node] and not visited[neighbor]:
if dfs(neighbor):
return True
return False
return dfs(start)
# 示例用法
graph = [[1, 3], [0, 2], [0, 1, 3], [3]]
start = 0
end = 3
maxJump = 2
print(canReachDestination(graph, start, end, maxJump))
```
### JavaScript 示例代码
```javascript
function canReachDestination(graph, start, end, maxJump) {
const n = graph.length;
const visited = new Array(n).fill(false);
function dfs(node) {
if (node === end) return true;
visited[node] = true;
for (let neighbor = Math.max(0, node - maxJump); neighbor <= Math.min(n - 1, node + maxJump); neighbor++) {
if (graph[node].includes(neighbor) && !visited[neighbor]) {
if (dfs(neighbor)) return true;
}
}
return false;
}
return dfs(start);
}
// 示例用法
const graph = [[1, 3], [0, 2], [0, 1, 3], [3]];
const start = 0;
const end = 3;
const maxJump = 2;
console.log(canReachDestination(graph, start, end, maxJump));
```
**码小课**网站中有更多关于算法和数据结构的相关内容分享给大家学习，涵盖了广度优先搜索、深度优先搜索、图论等多种算法的详细解析和实际应用案例。