上次在Hero in maze中我把从白书上学到的BFS分享了一下。但是白书上的《走迷宫》其实是输出走出迷宫路径的。如果想要更好地学习BFS。请看如何打印出拯救公主的路径。
代码如下：
#include <stdio.h>
#include <memory.h>
int q[900], la_dir[30][30], dir[900];//数组q[max*max]作为队列，保存当前位置 ,la_dir数组用于保存最后一次移动的方向，dir数组保存每一步的方向
int mat[30][30], vis[30][30], fa[30][30];//数组fa保存当前位置的父结点
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//数组dx,dy保存当前位置的偏移量
int sx, sy, ox, oy, n, m;
char s[30], name[4] = {'U','R','D','L'};
void print(int x, int y){//用于打印走出迷宫最短路径，x、y初始为公主的位置
int c = 0;//保存需要打印的路径个数
for(;;){//对成功救出公主的路径进行探索，每一个结点查找到它的父结点
int fx = fa[x][y] / m;//fx更新为其父结点位置
int fy = fa[x][y] % m;
if(fx == x&&fy == y)//当前结点与其父结点相等，说明到了起点
break;
dir[c++] = la_dir[x][y];//保存从终点到起点的路径
x = fx;//x更新为当前结点的父结点
y = fy;
}
while(c--)
printf("%c->",name[dir[c]]);//逆向输出所保存的路径
puts("");
}
void bfs(int x, int y){//通过BFS制作一个最短通路
int fron = 0, rear = 0;//队首、队尾指针初始化
int d, u;
u = x * m + y;//记录起点的位置
vis[x][y] = 1;//做已访问标记
fa[x][y] = u;//fa保存起点位置，自己作为自己的父结点
q[rear++] = u;//起点进入队列， 移动到队首，队尾指针后移
while(fron < rear){//判断队列是否为空
u = q[fron++];//此时u更新为当前队首位置，队首元素出列（先进先出）
x = u / m;//提取当前位置的横坐标
y = u % m;//提取当前位置的纵坐标
for(d = 0; d < 4; d++){//上下左右四个方向各偏移一次
int nx = x + dx[d], ny = y + dy[d];//下标偏移
if(nx >= 0&&nx < n&&ny >= 0&&ny < m&&mat[nx][ny]&& !vis[nx][ny]){//如果偏移后结点未曾访问且可以走通，则访问此结点
int v = nx * m + ny;//保存偏移位置
q[rear++] = v;//偏移位置进入队尾
vis[nx][ny] = 1;//做已访问标记
fa[nx][ny] = u;//保存偏移位置的父结点
la_dir[nx][ny] = d;//保存当前偏移方向，0：上 1：右 2：下 3：左
}
}
}
}
int main(){
int i, j;
memset(mat, 0, sizeof(mat));
memset(vis, 0, sizeof(vis));
scanf("%d%d", &n, &m);
for(i = 0; i < n; i++){
scanf("%s", s);//按行输入迷宫地图
for(j = 0; j < m; j++){
switch(s[j]){
case '*':mat[i][j] = 0;break;
case '.':mat[i][j] = 1;break;
case 'S':mat[i][j] = 1;sx = i;sy = j;break;
case 'P':mat[i][j] = 1;ox = i;oy = j;break;
}
}
}
bfs(sx, sy);
print(ox, oy);
return 0;
}