首页 > 代码库 > A - 迷宫问题
A - 迷宫问题
Description
定义一个二维数组：
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
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 00 1 0 1 00 0 0 0 00 1 1 1 00 0 0 1 0
Sample Output
(0, 0)(1, 0)(2, 0)(2, 1)(2, 2)(2, 3)(2, 4)(3, 4)(4, 4)
1 #include<cstdio> 2 #include<string.h> 3 using namespace std; 4 int maze[5][5]; 5 int q[10000]; 6 int dx[4]={-1,1,0,0}; 7 int dy[4]={0,0,-1,1}; 8 int vis[5][5]; 9 int fa[5][5],dist[5][5],dir[5][5];10 int dirt[10000];11 int zuobiao[10000];12 void bfs(int x,int y)//(x,y)是起点13 {14 int front=0,rear=0,d,u;15 u=5*x+y;16 vis[x][y]=1;fa[x][y]=u;dist[x][y]=0;17 q[rear++]=u;18 while(front<rear)19 {20 u=q[front++];21 x=u/5;y=u%5;22 if(x==4&&y==4) break;23 for(d=0;d<4;d++)24 {25 int nx=x+dx[d],ny=y+dy[d];26 if(nx>=0&&nx<5&&ny>=0&&ny<5&&!maze[nx][ny]&&!vis[nx][ny])27 {28 int v=nx*5+ny;29 q[rear++]=v;30 vis[nx][ny]=1;31 fa[nx][ny]=u;32 dist[nx][ny]=dist[x][y]+1;33 dir[nx][ny]=d;34 }35 }36 }37 }38 39 void print_path(int x,int y)40 {41 int c=0;42 for(;;)43 {44 int fx=fa[x][y]/5;45 int fy=fa[x][y]%5;46 if(fx==x&&fy==y) break;47 dirt[c++]=dir[x][y];48 zuobiao[c-1]=fa[x][y];49 x=fx;50 y=fy;51 }52 printf("(0, 0)\n");53 while(c--)54 printf("(%d, %d)\n",zuobiao[c]/5+dx[dirt[c]],zuobiao[c]%5+dy[dirt[c]]);55 }56 57 int main()58 {59 int i,j;60 for(i=0;i<5;i++)61 for(j=0;j<5;j++)62 {63 scanf("%d",&maze[i][j]);64 }65 bfs(0,0);66 print_path(4,4);67 return 0;68 }
A - 迷宫问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。