迷宮問題 Time Limit:?1000MS ? Memory Limit:?65536K Total Submissions:?39168 ? Accepted:?21898 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 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)\n",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 }

?

轉載于:https://www.cnblogs.com/tingtin/p/10513543.html

總結

以上是生活随笔為你收集整理的poj 3984的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。