3752:走迷宮
查看提交統計提示提問
總時間限制: ?1000ms ?內存限制: ?65536kB
描述
一個迷宮由R行C列格子組成，有的格子里有障礙物，不能走；有的格子是空地，可以走。
給定一個迷宮，求從左上角走到右下角最少需要走多少步(數據保證一定能走到)。只能在水平方向或垂直方向走，不能斜著走。
輸入
第一行是兩個整數，Ｒ和Ｃ，代表迷宮的長和寬。（ 1<= R，C <= 40)
接下來是Ｒ行，每行Ｃ個字符，代表整個迷宮。
空地格子用'.'表示，有障礙物的格子用'#'表示。
迷宮左上角和右下角都是'.'。
輸出
輸出從左上角走到右下角至少要經過多少步（即至少要經過多少個空地格子）。計算步數要包括起點和終點。
樣例輸入
5 5
..###
#....
#.#.#
#.#.#
#.#..
樣例輸出
9
---------------------------------------------------------------------------------------------------------------------------------

#include<bits/stdc++.h>
using namespace std;
int ss[105][105],flag[105][105];
int dx[12]={0,1,0,-1};
int dy[12]={1,0,-1,0};//上下左右?
int main()
{
??? ?char ch;
?? ?int que[10005][4]={0},x1,y1,i,j;
?? ?int s=1,e=1;
?? ?memset(ss,-1,sizeof(ss));//將ss中當前位置后面的sizeof(ss)個字節?
? ? que[1][1]=1;
?? ?que[1][2]=1;
?? ?que[1][3]=0;
? ? cin>>x1>>y1;//輸入迷宮大小?
? ? for(i=1;i<=x1;i++)
? ? {
? ?? ??? ?for(j=1;j<=y1;j++)
? ?? ??? ?{
? ?? ??? ? ??? ?cin>>ch;//輸入迷宮?
? ?? ??? ??? ?if(ch=='.')
? ? ?? ??? ??? ?flag[i][j]=0;//判斷是否能走?
? ??? ??? ??? ?else
? ? ?? ??? ?flag[i][j]=1;?
? ?? ??? ?}
? ?? ?}
??? ?while(s<=e)
??? ?{
??? ??? ?for(int d=0;d<=11;d++)
??? ??? ? {
? ??? ??? ??? ?int x=que[s][1]+dx[d];
? ??? ??? ??? ?int y=que[s][2]+dy[d];
? ??? ??? ??? ?if(x>0 && x<=100 && y>0 && y<=100 && flag[x][y]==0)
? ??? ??? ??? ?{
? ? ?? ??? ??? ?if(ss[x][y]==-1)
? ??? ??? ??? ??? ? {
? ? ??? ??? ??? ??? ?ss[x][y]=que[s][3]+1;
? ? ??? ??? ??? ??? ?e++;
? ? ?? ??? ??? ??? ? que[e][1]=x;
? ? ??? ??? ??? ??? ?que[e][2]=y;
? ? ??? ??? ??? ??? ?que[e][3]=ss[x][y];//套廣度優先搜索模板?
? ? ??? ??? ??? ??? ?if(ss[x1][y1]>0)
? ? ??? ??? ??? ??? ?{
? ? ? ?? ??? ??? ??? ??? ?cout<<ss[x1][y1]+1<<endl;//由于沒有算第一步，所以將答案加一?
? ??? ??? ??? ??? ??? ??? ?return 0;
?? ??? ??? ??? ? ? ? }
? ? ?? ??? ??? ?}
? ??? ??? ??? ? }
? ?? ??? ? }
? ? s++;
? ?? ?}
??? ?return 0;?
}

總結

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

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