1255：迷宫问题
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
定义一个二维数组：
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表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
【输入】
一个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
【输出样例】
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
1. #include <iostream> 2. #include <cstdio> 3. #include <cstring> 4. #include <algorithm> 5. using namespace std; 6. int map[6][6],p[50][4],m[50]; 7. int xx[4]={-1,1,0,0}; 8. int yy[4]={0,0,-1,1}; 9. int x,y,t=0,w=1; 10. void bfs(int a,int b){ 11. map[a][b]=1; 12. p[1][1]=a,p[1][2]=b,p[1][3]=0; 13. while(w>t){ 14. t++; 15. for(int i=0;i<4;i++){ 16. x=p[t][1]+xx[i]; 17. y=p[t][2]+yy[i]; 18. if(x>=0&&x<5&&y>=0&&y<5&&map[x][y]==0){ 19. w++;p[w][1]=x;p[w][2]=y; 20. p[w][3]=t;map[x][y]=1; 21. if(x==4&&y==4)return; 22. } 23. } 24. } 25. } 26. int main(int argc, char *argv[]) 27. { 28. for(int i=0;i<5;i++) 29. for(int j=0;j<5;j++) 30. scanf("%d",&map[i][j]); 31. bfs(0,0); 32. int k=0; 33. while(w>=1){ 34. k++;m[k]=w;w=p[w][3]; 35. } 36. for(int i=k;i>=1;i--) 37. printf("(%d, %d)\n",p[m[i]][1],p[m[i]][2]); 38. return 0; 39. }
