求最短路问题，但是需要打印路径，那么就需要把路径存下来，可以用结构体来存，这里我用的是pair。最后输出路径的时候是一个递归过程，理解不了的可以手动模拟一下，样例也不长。
AC代码：
代码语言：javascript复制#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
pair<int,int> Path[6][6],Now,Next; // Path数组用来标记路径
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
bool vis[6][6];
int MAP[6][6];
int step;
void bfs(){
step = 0;
memset(vis,0,sizeof(vis));
queue<pair<int,int> >q;
q.push(make_pair(0,0));
while(!q.empty()){
Now = q.front();
q.pop();
if(Now.first == 4 && Now.second == 4) return ;
for(int i=0;i<4;i ){
Next.first = Now.first dir[i][0];
Next.second = Now.second dir[i][1];
if(Next.first>=0&&Next.second>=0&&Next.first<5&&Next.second<5&&MAP[Next.first][Next.second]==0&&!vis[Next.first][Next.second]){
vis[Next.first][Next.second] = 1;
Path[Next.first][Next.second].first = Now.first; // 将Path数组的Next保存为上一个点的坐标Now
Path[Next.first][Next.second].second = Now.second;
q.push(make_pair(Next.first,Next.second));
}
}
}
}
void output(int x,int y){ // 递归过程
if(x == 0 && y == 0){
printf("(%d, %d)n",x,y);
return ;
}
output(Path[x][y].first,Path[x][y].second);
printf("(%d, %d)n",x,y);
}
int main()
{
for(int i=0;i<5;i ){
for(int j=0;j<5;j ){
scanf("%d",&MAP[i][j]);
}
}
bfs();
output(4,4);
return 0;
}
