题目描述

纯水贴
当你站在一个迷宫里的时候，往往会被错综复杂的道路弄得失去方向感，如果你能得到迷宫地图，事情就会变得非常简单。

假设你已经得到了一个 $n×m$ 的迷宫的图纸，请你找出从起点到出口的最短路。

输入格式
第一行是两个整数 $n$ 和 $m$，表示迷宫的行数和列数。

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

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

样例

3 3
S#T
.#.
...

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
typedef pair<int, int>PII;
const int N = 110;
char mp[N][N];//迷宫地图
int d[N][N];//步数
queue<PII>q;
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };//表示方向
int n,m;
int sx,sy,ex,ey;
int  bfs(int x,int y) {
    q.push({x,y});
    mp[x][y] = '#';
    d[x][y] = 0;//起点也有步数，步数为1
    while (q.size()) {//经典bfs模板
        PII t = q.front();
        int xx = t.first,yy = t.second;
        q.pop();
        if (xx == ex && yy == ey) {
        return d[xx][yy];//到达右下角是输出
    }
        for (int i = 0; i < 4; i++) {
        int nx = xx + dx[i];
        int ny = yy + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && (mp[nx][ny] == '.'|| mp[nx][ny] == 'T')) {
            mp[nx][ny] = '#';

            d[nx][ny] = d[xx][yy] + 1;q.push({nx,ny});
        }
    }
    }
    return -1;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            cin >> mp[i][j];
            if(mp[i][j]=='S')sx=i,sy=j;
            else if(mp[i][j]=='T')ex=i,ey=j;
        }

    cout<<bfs(sx,sy);


    return 0;
}