题目描述补充

地图跳跃

在一个由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 示例代码

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 示例代码

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 示例代码

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));

码小课网站中有更多关于算法和数据结构的相关内容分享给大家学习，涵盖了广度优先搜索、深度优先搜索、图论等多种算法的详细解析和实际应用案例。