【題目描述】

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

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

【輸入】

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

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

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

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

【輸出】

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

【輸入樣例】

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

【輸出樣例】

9

【源程序】

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 101 #define MOD 2520 #define E 1e-12 using namespace std; int r,c; char a[N][N]; bool vis[N][N]; int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; struct node {int x;int y;int step; }q[N*100]; void bfs(int sx,int sy,int ex,int ey) {int head=1,tail=1;memset(vis,0,sizeof(vis));vis[sx][sy]=1;q[tail].x=sx;q[tail].y=sy;q[tail].step=1;tail++;while(head<tail){int x=q[head].x;int y=q[head].y;int step=q[head].step;if(x==ex&&y==ey){printf("%d\n",step);break;}for(int i=0;i<4;i++){int nx=x+dir[i][0];int ny=y+dir[i][1];if(nx>=0&&nx<r&&ny>=0&&ny<c&&vis[nx][ny]==0&&a[nx][ny]=='.'){vis[nx][ny]=1;q[tail].x=nx;q[tail].y=ny;q[tail].step=step+1;tail++;}}head++;} } int main() {scanf("%d%d",&r,&c);for(int i=0;i<r;i++)scanf("%s",a[i]);bfs(0,0,r-1,c-1);return 0; }

?

總結

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

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