在图中找到 2 个给定城市之间的路径但有条件（需要在 K 步后访问检查站城市）

Question

我刚学了DFS、BFS和其他一些最短路径算法，但我无法解决这个练习。

有些城市有粮食供应。有些人没有。我们想从“起点”走到“终点”，但条件是我们可以在运行没有食物之前最多走 K 步。

(* 表示城市有食物供应可以领取)

例如，对于 K = 3 的情况

我们不能从A到G，因为一路上没有食物供应，所以我们死在了D市（3步没有食物）

A* ----B----C----D----E----F----G*

但是如果C市和F市有粮食供应，我们可以从A市到G市，在C市和F市领取粮食，然后继续到G市

A* ----B----C* ----D----E----F* ----G*

有什么想法吗？

（我们可以假设起点和终点总是包含食物供应）

(食物不叠加，捡到最后一个食物3步后死亡)

（不能多次访问城市）

Answer 1

拿一个数组，假设它是arr[节点数][距离]并标记为-1，现在从a开始，这里的节点数表示你在哪个节点上，distance表示距离多远从最近的食物节点开始，现在运行 a 上的 dfs，如果你在一个节点上旅行，假设是 b，与最近的食物节点的距离假设为 2，标记 arr[node b][2]=1( 1 表示它已经走过），现在如果你再次以相同的距离 2 到达节点 b（可能来自其他节点而不是节点 a），你会说我无法通过这条路径到达终点节点，现在如果你到达任何食物节点让我们称它为 c，使距离为 0 即标记 arr[c 节点][0]=1，现在如果你能够以这种方式到达最终节点，则成功，否则你无法到达最终节点。这是一个示例算法，

void funct(int node,int distance,int max_distance,int final_node){
    if(node==final_node):
        final_node can be reached
    if(distance>max_distance):
         return
    if(node == food_node):
        dist=0
    else:
        dist=distance
    if (arr[node][dist]==1):
        return
    for all the nearby node:
        arr[node][dist]=1
        funct(nearby node,dist+1,max_distance,final_node)

你这里的最终节点是G，max_distance是3，arr是二维数组

在图中找到 2 个给定城市之间的路径但有条件（需要在 K 步后访问检查站城市）

Find path between 2 given city in graph but with condition ( need to visit checkpoint city after K step)

graph-algorithm