Question

C语言对于用bfs求最短路径的同时，如何记录路径

rt 例如一个人走迷宫，最短路径长度为5，路径为上上上左左，这个路径怎么求，求代码或者思路都ok

Answer 1

比如地图为二维数组map[n][m],记录起点到每个点的最短路径(这个bfs得到),那么可以从终点倒推,即若终点为x1,y1,dist[x1][y1]=d,(xi ,yi)为与(x1,y1)相连的点,若dist[xi][yi]==d-1,那么可以从(xi,yi)走到(x1,y1),然后继续找下去,直到找到起点.可以dfs实现.