1254：走出迷宮

時間限制: 1000 ms ??? ??? 內(nèi)存限制: 65536 KB
提交數(shù): 9105 ??? 通過數(shù): 4245

【題目描述】

當(dāng)你站在一個迷宮里的時候，往往會被錯綜復(fù)雜的道路弄得失去方向感，如果你能得到迷宮地圖，事情就會變得非常簡單。

假設(shè)你已經(jīng)得到了一個n×m的迷宮的圖紙，請你找出從起點到出口的最短路。

【輸入】

第一行是兩個整數(shù)n和m(1≤n,m≤100)，表示迷宮的行數(shù)和列數(shù)。

接下來n行，每行一個長為m的字符串，表示整個迷宮的布局。字符‘.’表示空地，‘#’表示墻，‘S’表示起點,‘T’表示出口。

【輸出】

輸出從起點到出口最少需要走的步數(shù)。

【輸入樣例】

3 3 S#T .#. ...

【輸出樣例】

6

【分析】

? ? ? ? 迷宮問題可以用dfs，也可以用bfs實現(xiàn)，本題數(shù)據(jù)量比較大，只能用bfs實現(xiàn)，dfs超時。

【參考代碼】

#include <iostream> #include <cstdio> #include <queue>using namespace std;char a[100][100]; // 原地圖 bool v[100][100]; // 訪問數(shù)組 struct point {int x,y; // 坐標(biāo)int step; // 步數(shù) };queue <point> r; // 申請隊列 int dx[4]={0,1,0,-1}; // 方向數(shù)組，右，下，左，上 int dy[4]={1,0,-1,0}; int startx,starty; // 起始點坐標(biāo) int p,q; // 終點坐標(biāo) int m,n;void bfs() {point s; // 初始化隊列s.x=startx;s.y=starty;s.step=0;r.push(s); // 起點入隊v[startx][starty]=1;while(!r.empty()) // 判斷隊列是否為空 {point t,tmp;t=r.front();if(t.x==p && t.y==q) // 判斷是否是終點 {cout << t.step << endl;return;}for(int k=0;k<4;k++) // 四個方向 {tmp.x=t.x+dx[k];tmp.y=t.y+dy[k];if(tmp.x>=1 && tmp.x<=m && tmp.y>=1 && tmp.y<=n && a[tmp.x][tmp.y]=='.' && v[tmp.x][tmp.y]==false) // 判斷能不能走 {// 入隊處理tmp.step=t.step+1;r.push(tmp); // 入隊 v[tmp.x][tmp.y]=true; // 標(biāo)記 }}r.pop(); // 拓展完了，需要將隊首元素出隊} } int main() {int i,j;scanf("%d%d",&m,&n);getchar();for(i=1;i<=m;i++){for(j=1;j<=n;j++){scanf("%c",&a[i][j]); // '.'表示空地，'#'表示障礙物if(a[i][j]=='S'){startx=i;starty=j;a[i][j]='.';}if(a[i][j]=='T'){p=i;q=j;a[i][j]='.';}}getchar();}v[startx][starty]=true;bfs();return 0; }

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

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。