c - Dijkstra，Bellman Ford 在双阵列 map 上的应用

Question

我输入了这样一张 map :

int map_w = 40;
int map_h = 20;
char map[20][40] = {
    {'c', 'c', 'c', 'c', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'c', 'c', 'n', 'n', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'c', 'c', 'c', 'c', 'c', 'n', 'h', 'n', 'n'},
    {'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'n', 'c', 'n', 'n', 'c', 'c', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'n', 'c', 'n', 'n', 'h', 'h', 'n'},
    {'c', 'c', 'c', 'c', 'n', 'c', 'n', 'n', 'c', 'c', 'h', 'n', 'n', 'c', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'c', 'c', 'c', 'c', 'c', 'c', 'h', 'h', 'n'},
    {'h', 'h', 'h', 'c', 'c', 'c', 'c', 'c', 'c', 'h', 'h', 'n', 'c', 'n', 'n', 'h', 'h', 'h', 'h', 'n', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'h', 'h', 'n'},
    {'h', 'h', 'h', 'h', 'c', 'c', 'c', 'n', 'c', 'c', 'h', 'c', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'n', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h'},
    {'h', 'h', 'h', 'h', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'n', 'n', 'c', 'h', 'h', 'h', 'c', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'n', 'c', 'h', 'h', 'n', 'h', 'n', 'h', 'n'},
    {'n', 'h', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'n', 'h', 'h', 'n', 'h', 'h', 'h', 'h'},
    {'c', 'c', 'n', 'c', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'n', 'h', 'h', 'h', 'p', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h'},
    {'c', 'c', 'n', 'c', 'n', 'c', 'c', 'n', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'c', 'c', 'c', 'c', 'n', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'c', 'h', 'h', 'h', 'h', 'n', 'h'},
    {'c', 'c', 'c', 'n', 'c', 'c', 'c', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'h', 'c', 'c', 'c', 'c', 'c', 'n', 'n', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'n', 'h', 'p', 'h', 'h', 'h'},
    {'c', 'c', 'c', 'n', 'c', 'c', 'c', 'c', 'c', 'n', 'c', 'c', 'c', 'c', 'h', 'h', 'c', 'n', 'n', 'n', 'c', 'c', 'c', 'd', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'c', 'h', 'h', 'h', 'h', 'h', 'h'},
    {'c', 'c', 'n', 'c', 'c', 'n', 'n', 'c', 'c', 'c', 'c', 'h', 'c', 'h', 'h', 'n', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'h', 'h', 'h', 'h', 'n', 'h', 'n', 'c', 'h', 'h', 'h', 'h', 'h', 'h'},
    {'c', 'c', 'n', 'n', 'c', 'n', 'c', 'n', 'c', 'n', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'n', 'h', 'n', 'c', 'h', 'h', 'n', 'h', 'n', 'h'},
    {'n', 'c', 'c', 'n', 'c', 'n', 'n', 'n', 'c', 'n', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'n', 'c', 'c', 'n', 'c', 'h', 'h', 'h'},
    {'n', 'c', 'n', 'n', 'c', 'n', 'c', 'n', 'c', 'p', 'h', 'h', 'h', 'n', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'n', 'c', 'c', 'c', 'n', 'c', 'h', 'h', 'h'},
    {'n', 'n', 'c', 'c', 'c', 'c', 'n', 'n', 'c', 'c', 'c', 'c', 'h', 'h', 'c', 'h', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'h', 'c', 'c', 'c', 'n', 'n', 'c', 'c', 'n', 'n', 'h', 'h', 'n'},
    {'n', 'n', 'n', 'c', 'c', 'n', 'n', 'n', 'c', 'h', 'h', 'c', 'h', 'n', 'c', 'h', 'n', 'n', 'c', 'n', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'c', 'c', 'c', 'n', 'n', 'c', 'c', 'n', 'h', 'h', 'n'},
    {'n', 'n', 'n', 'n', 'n', 'n', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'c', 'c', 'c', 'c', 'n', 'n', 'c'},
    {'n', 'n', 'c', 'c', 'n', 'c', 'n', 'n', 'h', 'h', 'h', 'h', 'h', 'c', 'c', 'n', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'c', 'n', 'n', 'n', 'c', 'n', 'n', 'n', 'c', 'n', 'n', 'n', 'c', 'n', 'n', 'c', 'n'},
    {'c', 'c', 'c', 'c', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'n', 'c', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'n', 'n', 'c', 'n', 'n', 'c', 'n', 'c', 'c', 'n', 'n', 'n', 'n', 'n'}
};

这是 map 的图像:

数组中的字符对应于每个正方形，也就是说，灰色是 h，这是一 block 我不能走的石头。棕色是长度为 1 的正常路径 (c) 绿色是长度为 2 的森林 (n)

然后 d 是龙，p 是公主，我必须先找到到龙然后到公主的最短路径，然后返回准确的最短路径..

所以我的第一个问题是，是否有某种方法可以将此输入输入一些修改后的 Dijkstra、Bellman-Ford 或其他算法？或者我必须首先为每个正方形建立一个连接，从正方形 1,2 我可以转到 1,1 并且长度为 2，然后到 2,2 并且长度为 2，或者我可以简单地以某种方式运行算法双数组??

问题 2 你建议使用哪种算法？我想到了 Bellman Ford，虽然我没有负方 block ，但我需要返回确切的路径，这非常容易，这要归功于在 Bellman Ford 中维护的数组 pi，但我愿意接受任何建议，因为我刚刚进入图论。

Answer 1

我建议你仔细看看A* .

这是一种简单而有效的查找路径的方法，尤其是在二维网格中。