题目

如下图12×12方格图，找出一条自入口（2，9）到出口（11，8）的最短路径。

输入
第一行为一个数n，表示迷宫大小
第二行为4个数，表示起点和终点
第三起为n*n的矩阵，0表示通路，1表示墙。
输出
第一行为路径（见样例)
第二行为总的步数

思路

（表示不会用循环队列）用一个队列存要搜的节点，搜过的节点删除。从前往后搜，搜到头h==尾t的时候就说明搜完了。还有步数先不统计，用查找父节点的方式一个一个倒回去。

代码

#include using namespace std; const int maxn=1000; int qx,qy,zx,zy,n,f[maxn*maxn]={0},a[maxn] [maxn],fx[maxn*maxn][2]; //q=起，z=终，fx存当前位置，f存队列 int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1},h=0,t=1,s;//方向x，y，头，尾，数量 bool pdd(int i,int j){ //判断当前节点是否可以走 if(i>=1&&i<=n&&j>=1&&j<=n&&a[i][j]==0){ for(int k=1;kif(fx[k][0]==i&&fx[k][1]==j) return false; return true; } return false; } void po(int k){ //输出与统计数量 if(k==0) return; s++; po(f[k]); if(k!=t) printf("(%d,%d)->",fx[k][0],fx[k][1]); else printf("(%d,%d) ",fx[k][0],fx[k][1]); } void bfs(){ fx[1][0]=qx;fx[1][1]=qy;f[1]=0; //初始化 do{ h++; //头+1 for(int k=1;k<=4;k++) //四个方向搜 if(pdd(fx[h][0]+dx[k],fx[h][1]+dy[k])==true){ //此节点可以走 t++; //存入队列 f[t]=h; fx[t][0]=fx[h][0]+dx[k]; fx[t][1]=fx[h][1]+dy[k]; a[fx[t][0]][fx[t][1]]=1; if(fx[t][0]==zx&&fx[t][1]==zy){ //找到了目标 s=0; po(t); printf("%d",s); return; } } } while(hint main(){ scanf("%d%d%d%d%d",&n,&qx,&qy,&zx,&zy);//读入 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]); bfs(); }