迷宫问题DFS写法 BFS写法

定义一个二维数组： int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。 Input 一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。 Output 左上角到右下角的最短路径，格式如样例所示。 Sample Input 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 Sample Output (0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4) DFS写法 #include<iostream> #include<cstring> #include <cstdio> using namespace std; int a[6][6]; int p,q,t,ans,n; int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}}; struct node //用来记录走过的路径 { int a; int b; } s[905]; int dfs(int i,int j) { if(a[i][j]==1) return 0; if(i<0||i>4||j<0 ||j>4) return 0; a[i][j]=1; //走过之后 把这个位置 标记成走过的 s[ans].a=i; s[ans++].b=j; if(i==4 && j==4) return 1; //全部走完 if(dfs(i+1,j)||dfs(i,j+1)||dfs(i-1,j)||dfs(i,j-1)) return 1; //优先走下和右的方向 再走左和上 这样一遍就可以成功了 a[i][j]=0; //回溯回来之后把这个位置 重新标记为未走过的 ans--; //记录走过的路径也返回去 return 0; } int main() { for(int i=0;i<5;i++) for(int j=0;j<5;j++) cin>>a[i][j]; ans=0; dfs(0,0); for(int i=0;i<ans;i++) printf("(%d, %d)\n",s[i].a,s[i].b); return 0; } BFS写法 #include <iostream> #include <queue> #include <cstring> #include <cstdio> #include <stack> using namespace std; int maze[6][6]; //迷宫地图 int visit[6][6]; //判断是够拜访过这个点 int step[6][6]; //标记步数 int dir[4][2]={{-1,0},{0,-1},{0,1},{1,0}}; struct node { int x; int y; }; queue <node> p; int nyj(int a,int b) //判断是否越界 { if(a>=0 && a<5 && b>=0 && b<5) return 1; else return 0; } void print(int i,int j) //用深搜从尾找到头 把最优路径输出 { if(i==0 && j==0) { printf("(%d, %d)\n",i,j); return ; } for(int x=0;x<4;x++) { int xx=i+dir[x][0]; int yy=j+dir[x][1]; if(nyj(xx,yy) && !maze[xx][yy] && step[xx][yy]==step[i][j]-1) print(xx,yy); } printf("(%d, %d)\n",i,j); } void BFS(int i,int j) { node n; n.x=i; n.y=j; p.push(n); step[i][j]=1; visit[i][j]=1; while(!p.empty()) { n=p.front(); //通过队列 每次讲队列的第一个元素取出来 进行搜索 p.pop(); for(int x=0;x<4;x++) { int xx=n.x+dir[x][0]; int yy=n.y+dir[x][1]; if(nyj(xx,yy) && maze[xx][yy]==0 && !visit[xx][yy]) { visit[xx][yy] =1; step[xx][yy]=step[n.x][n.y]+1; node a; a.x=xx; a.y=yy; p.push(a); //找到符合的进队列 } } } /*for(int ii=0;ii<5;ii++) //输出step 可以更好地理解一下广搜 { for(int jj=0;jj<5;jj++) cout<<step[ii][jj]<<' '; cout<<endl; }*/ print(4,4); } int main() { for(int i=0;i<5;i++) for(int j=0;j<5;j++) cin>>maze[i][j]; memset(visit,0,sizeof(visit)); memset(step,0,sizeof(step)); BFS(0,0); return 0; }