poj 3984 迷宫问题（bfs）
| 迷宫问题
Description 定义一个二维数组：
它表示一个迷宫，其中的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) Source |
[Submit] [Go Back] [Status] [Discuss]
5*5的迷宫，从左上角到右下角，用广度优先搜索来做。。。
迷宫固定大小。。。
1 #include <iostream> 2 #include <cstdio> 3 #include <queue> 4 #include <cstring> 5 #include <algorithm> 6 7 using namespace std; 8 9 struct node{ 10 int x,y; 11 int step; 12 int xed[25],yed[25]; 13 }; 14 15 int a[5][5]; 16 bool visable[5][5]; 17 int directx[4]={-1,1,0,0}; 18 int directy[4]={0,0,-1,1}; 19 20 void bfs(){ 21 memset(visable,true,sizeof(visable)); 22 node first; 23 first.x=0; 24 first.y=0; 25 first.step=0; 26 first.xed[first.step]=0; 27 first.yed[first.step++]=0; 28 visable[0][0]=false; 29 queue<node> que; 30 que.push(first); 31 while(!que.empty()){ 32 node now=que.front(); 33 que.pop(); 34 for(int i=0;i<4;i++){ 35 node next=now; 36 next.x+=directx[i]; 37 next.y+=directy[i]; 38 if(!visable[next.x][next.y]&&next.x<0||next.x>=5||next.y<0||next.y>=5||a[next.x][next.y]==1){ 39 continue; 40 } 41 next.xed[next.step]=next.x; 42 next.yed[next.step++]=next.y; 43 if(next.x==4&&next.y==4){ 44 for(int j=0;j<next.step;j++){ 45 printf("(%d, %d)\n",next.xed[j],next.yed[j]); 46 } 47 return ; 48 } 49 que.push(next); 50 visable[next.x][next.y]=false; 51 } 52 } 53 } 54 55 int main() 56 { 57 for(int i=0;i<5;i++){ 58 for(int j=0;j<5;j++){ 59 scanf("%d",&a[i][j]); 60 } 61 } 62 bfs(); 63 64 return 0; 65 }
投递理想汽车等公司10个岗位 >
