迷宫问题Time Limit : 2000/1000ms (Java/Other) Memory Limit : 131072/65536K (Java/Other)Total Submission(s) : 10056 Accepted Submission(s) : 5652Problem 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 Input0 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) SourcePKU 路径输出， 递归输出较为简洁。
ac代码：
#include#include #include using namespace std;const int MAX = 10;struct point{ int x,y,pre; }q[MAX];int front = 0, rear = 1, sx, sy, ex, ey;int arr[MAX][MAX];int dx[4]={ 1, 0, -1, 0}, dy[4] = { 0, 1, 0, -1};int n, m;void output(int i) { if(q[i].pre != -1) { output(q[i].pre); printf("(%d, %d)\n",q[i].x,q[i].y); }}void bfs(int sx,int sy){ q[front].x = sx; q[front].y = sy; q[front].pre = -1; arr[sx][sy] = 1; while(front < rear) //模拟； { for(int i=0;i<4;i++) { int nx = q[front].x + dx[i]; int ny = q[front].y + dy[i]; if(nx<0 || nx>=5 || ny<0 || ny>=5 || arr[nx][ny]) continue; else { arr[nx][ny] = 1; q[rear].x = nx; q[rear].y = ny; // printf("%d %d\n", q[rear].x, q[rear].y); q[rear++].pre = front; } if(nx == 4 && ny == 4) output(front); } front++; }}int main(){ for(int i=0;i<5;i++) for(int j=0;j<5;j++) scanf("%d",&arr[i][j]); printf("(0, 0)\n"); bfs(0,0); printf("(4, 4)\n"); return 0;}
1 /*输出迷宫路径， 要记录前驱，输出时是从开始到结尾，所以要处理一下。*/ 2 #include3 #include 4 #include 5 #include 6 using namespace std; 7 const int INF = 0x3f3f3f3f; 8 int minn = INF; 9 int map[10][10], Ax[10], Ay[10], ac[4][2] = { 0, 1, 0, -1, -1, 0, 1, 0};10 struct Rode11 {12 int x, y, step;13 } a, temp, ans, pre[20][20];14 15 bool Judge(Rode &temp)16 {17 if(temp.x >= 0 && temp.y >= 0 && temp.x < 5 && temp.y < 5 && map[temp.x][temp.y] == 0)18 return true;19 else20 return false;21 }22 void Bfs()23 {24 queue q; 25 a.x = 0; a.y = 0; a.step = 0;26 q.push(a); 27 map[0][0] = 1;28 while(!q.empty())29 {30 a = q.front();31 q.pop(); 32 temp = a;33 for(int i = 0; i < 4; i++)34 {35 temp.x = a.x + ac[i][0];36 temp.y = a.y + ac[i][1];37 temp.step = a.step + 1; 38 if(Judge(temp))39 {40 if(temp.x == 4 && temp.y == 4)41 {42 if(temp.step < minn)43 {44 minn = temp.step; 45 pre[4][4].x = a.x;46 pre[4][4].y = a.y;47 }48 continue;49 } 50 map[temp.x][temp.y] = 1;51 pre[temp.x][temp.y].x = a.x;52 pre[temp.x][temp.y].y = a.y;53 q.push(temp);54 }55 } 56 } 57 } 58 int main()59 {60 for(int i = 0; i < 5; i++)61 for(int j = 0; j < 5; j++)62 scanf("%d", &map[i][j]);63 Bfs();64 int x, y, k = 0;65 x = y = 4;66 while(1) 67 { 68 int tx,ty; 69 tx=x; 70 ty=y; 71 if(!pre[x][y].x&&!pre[x][y].y) 72 break; 73 Ax[k]=pre[tx][ty].x; 74 Ay[k++] = pre[tx][ty].y; 75 x=pre[tx][ty].x; 76 y=pre[tx][ty].y; 77 } 78 79 printf("(0, 0)\n"); 80 for(int i = k - 1; i >= 0; i--)81 printf("(%d, %d)\n", Ax[i], Ay[i]);82 printf("(4, 4)\n");83 return 0;84 }