迷宫问题（深搜⼴搜）题⽬描述：给出⼀个m*n的迷宫图和⼀个⼊⼝，⼀个出⼝。
编⼀个程序，打印⼀条从迷宫⼊⼝到出⼝的路径。
-1表⽰⾛不通，0表⽰能⾛，只能上下左右⾛；⽆路可⾛输出“no way”；样例输⼊：8 5-1 -1 -1 -1 -10 0 0 0 -1-1 -1 -1 0 -1-1 0 0 0 -1-1 0 0 1 -1-1 0 0 0 -1-1 -1 -1 0 -1-1 0 0 0 -12 18 48 5-1 -1 -1 -1 -10 0 0 0 -1-1 -1 -1 0 -1-1 0 0 0 -1-1 0 0 -1 -1-1 0 0 0 -1-1 -1 -1 -1 -1-1 0 0 0 -12 18 4样例输出：你⽐着我的试试呗。
【代码】1//深搜2 #include<iostream>3 #include<cstdlib>4 #include<cstdio>5using namespace std;6int n,m;7int mmap[100][100];//输⼊的迷宫8int a[100],b[100];//记录每⼀步的横纵坐标9int ckx,cky,rkx,rky,totstep,f;//出⼝x,y；⼊⼝x,y；10void dfs(int,int,int);//深搜11int main()12 {13 scanf("%d%d",&n,&m);//输出迷宫的⼤⼩14for(int i=1;i<=n;i++)15 {16for(int j=1;j<=m;j++)17 {18 scanf("%d",&mmap[i][j]);19 }20 }2122 scanf("%d%d%d%d",&rkx,&rky,&ckx,&cky);//输⼊⼊⼝和出⼝坐标23 dfs(rkx,rky,1);//从⼊⼝深搜，步数是1；24if(f)//如果能搜到输出步数25 {26for(int i=1;i<=totstep;i++)27 {28 cout<<a[i]<<","<<b[i]<<endl;29 }30 }31else32 printf("no way!");33return0;34 }35void dfs(int x,int y,int step)36 {37 a[step]=x;b[step]=y;//第⼀步的x,y；38 mmap[x][y]=1;//打标记39if(x==ckx&&y==cky)//到达终点40 {41 totstep=step;42 f=1;//标记43 }44else45 {46if(y!=m&&mmap[x][y+1]==0)dfs(x,y+1,step+1);//能向右⾛47if((!f)&&x!=n&&mmap[x+1][y]==0)dfs(x+1,y,step+1);//没⾛到终点（因为找到⼀条路就可以了），可以向下⾛ 48if(!f&&x!=1&&mmap[x-1][y]==0)dfs(x-1,y,step+1);//向左⾛49if(!f&&y!=1&&mmap[x][y-1]==0)dfs(x,y-1,step+1);//向上⾛50 }51 }52//⼴搜53 #include<iostream>54 #include<cstdlib>55 #include<cstdio>56using namespace std;57int qx,qy,zx,zy,n,m,f;//起点终点坐标，迷宫的⼤⼩和是否能⾛的标记58int mmap[100][100];59int dx[4]={0,1,0,-1},//能⾛的⽅向60 dy[4]={1,0,-1,0};61int qque[100][4];//队列62int pre[100];//记录前驱63void bfs();64void print(int);65int main()66 {67 scanf("%d%d",&n,&m);68for(int i=1;i<=n;i++)69for(int j=1;j<=m;j++)70 scanf("%d",&mmap[i][j]);71 scanf("%d%d%d%d",&qx,&qy,&zx,&zy);72 bfs();73if(!f)74 printf("no way!");75return0;76 }77void bfs()78 {79int head=0,tail=1,step=1;80 qque[1][1]=qx;qque[1][2]=qy;81do82 {83 head++;84for(int i=0;i<=3;i++)//寻找能⾛的位置85 {86int x=qque[head][1]+dx[i],87 y=qque[head][2]+dy[i];88if(x>=1&&y>=1&&x<=n&&y<=m&&mmap[x][y]==0)//没有超过边界并且没有⾛过；89 {90 mmap[x][y]=1;//标记不能⾛91 tail++;//⼊队92 qque[tail][1]=x;qque[tail][2]=y;93 pre[tail]=head;//记录前驱94if(x==zx&&y==zy)//到达终点输出95 {96 f=1;97 print(tail);98break;99 }100 }101 }102if(f)break;103 }while(head<tail);104 }105void print(int x)106 {107if(pre[x]!=x)108 print(pre[x]);109 cout<<qque[x][1]<<","<<qque[x][2]<<endl;110 }如果是深搜，记录路径就是每⼀步的横纵坐标⽤数组记录就可以了⼴搜路径就⽤记录前驱结点就可以了；。
