1255：迷宮問題

時間限制: 1000 ms ??? ??? 內存限制: 65536 KB
提交數: 7919 ??? 通過數: 3656

【題目描述】

定義一個二維數組：

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)

【分析】

? ? ? ? 這是典型的迷宮問題。用bfs實現，需要注意的事，廣搜到出口結點，一定存在著一條路徑通到出口，并且輸出走過的路徑，需要遞歸輸出所走路徑。

【參考代碼】

#include<iostream> #include<cstdio> #include<queue>using namespace std;struct node {int x;int y; }q[35][35]; //記錄走過的路徑 int dir[][2]={{1,0},{-1,0},{0,1},{0,-1}}; //方向數組 int vis[5][5]; //訪問數組 int maze[5][5]; //迷宮地圖 void print(int x, int y) //遞歸輸出路徑 {if(x==-1 && y==-1)return;print(q[x][y].x,q[x][y].y);printf("(%d, %d)\n",x,y); }void bfs() {vis[0][0]=-1;q[0][0].x=-1;q[0][0].y=-1;queue <node> r; //申請隊列 node s;s.x=0;s.y=0;vis[0][0]=1;r.push(s); //起點入隊 while(!r.empty()){node t,tmp;t=r.front();if(t.x==4 && t.y==4) //到達終點 {print(4,4);}for(int i=0;i<4;i++){int nx=t.x+dir[i][0];int ny=t.y+dir[i][1];if(nx>=0 && nx<5 && ny>=0 && ny<5 && (!vis[nx][ny]) && !(maze[nx][ny])){vis[nx][ny] = 1;tmp.x=nx;tmp.y=ny;r.push(tmp);q[nx][ny].x=t.x;q[nx][ny].y=t.y;}}r.pop();} } int main() {for(int i=0;i<5;i++)for(int j=0;j<5;j++)scanf("%d", &maze[i][j]);bfs();return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1255

總結

以上是生活随笔為你收集整理的信息学奥赛一本通（1255：迷宫问题）的全部內容，希望文章能夠幫你解決所遇到的問題。

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