我输入了这样一张 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,但我愿意接受任何建议,因为我刚刚进入图论。
最佳答案
我建议你仔细看看A* .
这是一种简单而有效的查找路径的方法,尤其是在二维网格中。
关于c - Dijkstra,Bellman Ford 在双阵列 map 上的应用,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20147378/