1252：走迷宮

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

【題目描述】

一個迷宮由R行C列格子組成，有的格子里有障礙物，不能走；有的格子是空地，可以走。

給定一個迷宮，求從左上角走到右下角最少需要走多少步(數(shù)據(jù)保證一定能走到)。只能在水平方向或垂直方向走，不能斜著走。

【輸入】

第一行是兩個整數(shù)，Ｒ和Ｃ，代表迷宮的長和寬。（ 1<= R，C <= 40)

接下來是Ｒ行，每行Ｃ個字符，代表整個迷宮。

空地格子用‘.’表示，有障礙物的格子用‘#’表示。

迷宮左上角和右下角都是‘.’。

【輸出】

輸出從左上角走到右下角至少要經(jīng)過多少步（即至少要經(jīng)過多少個空地格子）。計算步數(shù)要包括起點和終點。

【輸入樣例】

5 5 ..### #.... #.#.# #.#.# #.#..

【輸出樣例】

9

【分析】

? ? ? ? 典型的迷宮問題，四個方向探索，從(1,1)探索到(n,m)。

【參考代碼】

#include <iostream> #include <queue>using namespace std;const int N=110; struct point {int x,y; //坐標(biāo) int step; //步數(shù) }; char a[N][N]; //(1,1)開始地圖 int vis[N][N]; //訪問數(shù)組 int m,n; //迷宮行數(shù)和列數(shù) int startx,starty; //入口坐標(biāo) int decx,decy; //出口坐標(biāo) int dx[4]={0,1,0,-1}; //方向數(shù)組，右，下，左，上 int dy[4]={1,0,-1,0};void bfs() {queue <point> r; //申請隊列point start; //初始化隊列 start.x=startx;start.y=starty;start.step=1;r.push(start); //起點入隊 vis[startx][starty]=1;while(!r.empty()) //判斷隊列是否為空 {int x=r.front().x; //獲得隊首元素int y=r.front().y;if(x==decx && y==decy){cout << r.front().step;}for(int i=0;i<4;i++) //四個方向擴展{int nx,ny;nx=x+dx[i];ny=y+dy[i];if(a[nx][ny]=='.' && vis[nx][ny]==0) //判斷能不能走 {point temp;temp.x=nx;temp.y=ny;temp.step=r.front().step+1;r.push(temp); //入隊vis[nx][ny]=1; // 標(biāo)記 }}r.pop();} }int main() {cin >> n >> m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin >> a[i][j];startx=1;starty=1;decx=n;decy=m;bfs();return 0; }

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

總結(jié)

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

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