迷宫问题
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 40547 | Accepted: 22591 |
Description
定义一个二维数组：
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 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 bool isw[5][5];//标记 8 int a[5][5];//地图 9 int next[4][2] = { 0, 1, 1, 0, 0, -1, -1, 0}; 10 11 struct Node{12 int x;13 int y;14 int s;//记录步数 15 short l[30];//记录路径 16 };17 18 Node bfs()19 {20 queue q;21 Node cur,nex;22 cur.x = 0; 23 cur.y = 0;24 cur.s = 0;25 isw[cur.x][cur.y] = true;26 //将起点入队 27 q.push(cur);28 while(!q.empty()){29 cur = q.front();30 q.pop();31 if(cur.x==4 && cur.y==4)//当走到4,4点时停止 32 return cur;33 for(int i=0;i<4;i++){34 int nx = cur.x + next[i][0];35 int ny = cur.y + next[i][1];36 if(nx < 0 || nx > 4 || ny < 0 || ny > 4){ //越界 37 continue;38 }39 if(!a[nx][ny] && !isw[nx][ny]){40 isw[nx][ny] = true;41 nex = cur;42 nex.x = nx;43 nex.y = ny;44 nex.s = cur.s + 1;45 nex.l[cur.s] = i;46 47 } 48 q.push(nex); 49 } 50 }51 return cur;52 }53 54 55 int main()56 {57 int i,j;58 for(i=0;i<5;i++){ //读入迷宫59 for(j=0;j<5;j++){60 scanf("%d",&a[i][j]);61 }62 }63 memset(isw,0,sizeof(isw));64 Node ans = bfs();//将最后一个点返回 65 int x,y;66 x = 0,y = 0;67 for(i=0;i<=ans.s;i++){68 printf("(%d, %d)\n",x,y);69 x+=next[ans.l[i]][0];70 y+=next[ans.l[i]][1];71 } 72 return 0;73 }