迷宮問題

Time Limit: 1000MS	?	Memory Limit: 65536K
Total Submissions: 31050	?	Accepted: 17826

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) #include<cstdio> #include<cstring> using namespace std; int mp[8][8],vis[8][8]; int ans;//輸出從起點到終點的步數 int pre[50];//記錄路徑 struct node {int x,y,step; }q[110];//隊列 int dic[4][2]={1,0,0,1,-1,0,0,-1};bool check(int x,int y) {if(x<0||x>=5||y<0||y>=5||vis[x][y]||mp[x][y])return 1;return 0; } //輸出路徑 void print(int head) {int next=pre[head];if(next==0){printf("(0, 0)\n");printf("(%d, %d)\n",q[head].x,q[head].y);return;}else print(next);printf("(%d, %d)\n",q[head].x,q[head].y); } void bfs() {q[0].x=0;q[0].y=0;q[0].step=0;pre[0]=-1;//vis[0][0]=1;int head=0,tail=1;while(head<tail){int x=q[head].x;int y=q[head].y;if(x==4&&y==4){ans=q[head].step;print(head);return;}for(int i=0;i<4;i++){int xx=x+dic[i][0];int yy=y+dic[i][1];if(check(xx,yy))continue;vis[xx][yy]=1;q[tail].x=xx;q[tail].y=yy;q[tail].step=q[head].step+1;pre[tail]=head;//記錄路徑tail++;//入隊}head++;//出隊}return; } int main() {for(int i=0;i<5;i++)for(int j=0;j<5;j++)scanf("%d",&mp[i][j]);ans=0;memset(vis,0,sizeof(vis));bfs();//printf("%d\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的POJ 3984 迷宫问题 BFS求最短路线+路径记录的全部內容，希望文章能夠幫你解決所遇到的問題。

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