问题 A: 走出迷宫(BFS)

时间限制: 1 Sec  内存限制: 128 MB
[提交] [状态]

题目描述

当你站在一个迷宫里的时候，往往会被错综复杂的道路弄得失去方向感，如果你能得到迷宫地图，事情就会变得非常简单。
假设你已经得到了一个n×m的迷宫的图纸，请你找出从起点到出口的最短路。

输入

第一行是两个整数n和m，表示迷宫的行数和列数。
接下来n行，每行一个长为m的字符串，表示整个迷宫的布局。字符.表示空地，#表示墙，S表示起点，T表示出口。

输出

输出从起点到出口最少需要走的步数。

样例输入 Copy

3 5
T..##
#.#.S
#...#

样例输出 Copy

7

提示

对于100%的数据，保证1≤n,m≤100，保证从起点出发一定能到达出口。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std; 
typedef long long ll; 
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int INF=0x3f3f3f3f;
const int maxn=110;
struct node{
    int x,y;
    int st;
};
int dir[4][2]={-1,0,1,0,0,-1,0,1};
char a[maxn][maxn];
int vis[maxn][maxn];
int n,m;
int bfs(int u,int v){
    node tmp,nex;
    tmp.x=u;
    tmp.y=v;
    tmp.st=0;
    queue<node>q;
    q.push(tmp);
    while(!q.empty()){
        tmp=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            nex.x=tmp.x+dir[i][0];
            nex.y=tmp.y+dir[i][1];
            nex.st=tmp.st+1;
            if(nex.x<0||nex.y<0||nex.x>n||nex.y>m||a[nex.x][nex.y]=='#'||vis[nex.x][nex.y]==1)continue;
            vis[nex.x][nex.y]=1;
            if(a[nex.x][nex.y]=='T'){
                return nex.st;
            }

            q.push(nex);
        }
    }
}
int main(){
    cin>>n>>m;
    int x1,y1;//起点 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j]=='S'){
                x1=i;
                y1=j;
            }
        }
    }
    int sum=bfs(x1,y1);
    cout<<sum<<endl;
}