- 总时间限制:
- 1000ms 内存限制:
- 65536kB
- 描述
-
当你站在一个迷宫里的时候,往往会被错综复杂的道路弄得失去方向感,如果你能得到迷宫地图,事情就会变得非常简单。
假设你已经得到了一个n*m的迷宫的图纸,请你找出从起点到出口的最短路。 输入 - 第一行是两个整数n和m(1<=n,m<=100),表示迷宫的行数和列数。 接下来n行,每行一个长为m的字符串,表示整个迷宫的布局。字符'.'表示空地,'#'表示墙,'S'表示起点,'T'表示出口。 输出
- 输出从起点到出口最少需要走的步数。 样例输入
-
3 3S#T.#....
样例输出 6 BFS,注意记录步数
1 #include2 using namespace std; 3 char a[505][505]; 4 int mx[5]={ 0,-1,1,0,0}; 5 int my[5]={ 0,0,0,-1,1}; 6 int vis[505][505]; 7 int N,M; 8 inline void ser(); 9 int x,y;10 int ANS=1e9;11 queue Qx,Qy,Qs;12 int main(){13 scanf("%d%d",&N,&M);14 for(int i=1;i<=N;i++){15 scanf("%s",a[i]+1);16 for(int j=1;j<=M;j++){17 if(a[i][j]=='S'){18 x=i; y=j;19 }20 }21 }22 Qx.push(x); Qy.push(y), Qs.push(0);23 vis[x][y]=1;24 ser();25 return 0;26 }27 inline void ser(){28 while(Qx.size()!=0&&Qy.size()!=0){29 int nowx=Qx.front();30 int nowy=Qy.front();31 int nows=Qs.front();32 Qx.pop(); Qy.pop(); Qs.pop();33 int tox,toy;34 for(int i=1;i<=4;i++){35 tox=nowx+mx[i];36 toy=nowy+my[i];37 if(vis[tox][toy]==0&&1<=tox&&tox<=N&&1<=toy&&toy<=M&&a[tox][toy]!='#'){38 vis[tox][toy]=1;39 if(a[tox][toy]=='T'){40 cout< <