|
迷宫问题
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]
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <iostream> 6 #include <algorithm> 7 #include <cmath> 8 #include <queue> 9 using namespace std; 10 #define pi acos(-1.0) 11 typedef long long ll; 12 const int N =1e4+100; 13 int a[10][10]; 14 bool vis[10][10]; 15 int px[10][10],py[10][10]; 16 int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; 17 void init() 18 { 19 memset(vis,0,sizeof(vis)); 20 memset(px,-1,sizeof(px));//不能初始化为0，因为横纵坐标李有0 21 memset(py,-1,sizeof(py)); 22 } 23 struct Node{ 24 int x,y,step; 25 Node(){} 26 Node(int x,int y,int step):x(x),y(y),step(step){} 27 }; 28 bool check(int x,int y){ 29 if(x>=0&&x<5&&y>=0&&y<5&&!vis[x][y]&&a[x][y]==0) 30 return true; 31 return false; 32 } 33 void print(int x,int y){ 34 if(px[x][y]!=-1&&py[x][y]!=-1){//必须都是-1，才表明到了(0,0) 35 print(px[x][y],py[x][y]); 36 } 37 printf("(%d, %d) ",x,y); 38 } 39 void bfs(Node nod) 40 { 41 queue<Node>Q; 42 Q.push(nod); 43 while(!Q.empty()){ 44 Node tmp=Q.front(); 45 Q.pop();//只要出现在queue里，就一定被标记了。因此不需要在标记tmp 46 if(tmp.x==4&&tmp.y==4){ 47 print(4,4); 48 break; 49 } 50 for(int i=0;i<4;i++){ 51 int x=tmp.x+dir[i][0]; 52 int y=tmp.y+dir[i][1]; 53 if(check(x,y)){ 54 vis[x][y]=1;//不标记的话，前面的点在不断变化，无法打印 55 px[x][y]=tmp.x;//(x,y)前面那个点的横坐标为tmp.x 56 py[x][y]=tmp.y; 57 Q.push(Node(x,y,tmp.step+1));//+1 58 } 59 } 60 } 61 } 62 int main() 63 { 64 for(int i=0;i<5;i++){ 65 for(int j=0;j<5;j++){ 66 scanf("%d",&a[i][j]); 67 } 68 } 69 init(); 70 vis[0][0]=1; 71
//vis[0][0]=1;
//对于样例来说，不写vis[0][0]==1的话。 (0,0)的前一个点是（1，0）,不是（-1，-1）。
//这样的话print 无限下去了。
//如果不打印的话，vis[0][0]可以不用==1的。
73 bfs(Node(0,0,0)); 74 return 0; 75 }