题目描述
这是 mengxiang000 和 Tabris 来到幼儿园的第四天，幼儿园老师在值班的时候突然发现某处发生火灾，而且火势蔓延极快。老师在第一时间发出了警报。位于幼儿园某处的 mengxiang000 和 Tabris 听到火灾警报声后拔腿就跑，不知道两人是否能够逃脱险境？
幼儿园可以看成是一个 N × M 的网格，网格中包含以下几种元素：
.：表示这是一块空地，是可以随意穿梭的。#：表示这是一块墙，是不可以走到这上边来的，但是可以被火烧毁。S：表示 mengxiang000 和 Tabris 的起始位置。E：表示幼儿园的出口。*：表示火灾发源地（保证输入只有一个火灾发源地）。
已知每秒有火的地方都会向周围八个格子（上下左右、左上、右上、左下、右下）蔓延火势。
mengxiang000 和 Tabris 每秒可以选择周围四个格子（上下左右）进行移动。
（假设两人这一秒行动完之后，火势才蔓延开）
根据已知条件，判断两人能否成功逃脱险境。如果可以，输出最短逃离时间，否则输出 T_T。
为了防止孩子们嬉戏中受伤，墙体是橡胶制作的，可以燃烧的哦。
输入描述
- 第一行输入一个整数 $t$，表示测试数据组数。
- 第二行输入两个整数 $n$ 和 $m$，表示幼儿园的大小。
- 接下来 $n$ 行，每行 $m$ 个字符，表示此格子是什么元素。
限制条件：
- $t \leq 200$
- $3 \leq n, m \leq 30$
- 保证图中有一个起点、一个出口、一个火灾源处。
输出描述
- 每组数据输出一行，如果两人能够成功到达出口，那么输出最短逃离时间，否则输出
T_T。
样例输入
3
5 5
*....
.....
..S#.
...E.
.....
5 5
...#*
..#S#
...##
....E
.....
5 5
.....
S....
..*#.
...E.
.....
样例输出
2
T_T
T_T
说明
为了防止孩子们嬉戏中受伤，墙体是橡胶制作的，可以燃烧的哦。
/**
* author: Egrvigrf
* created: 2024-05-24 13:46:06
**/
// #pragma GCC optimize(2)
// #pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ld pi = acosl(-1);
// #define int long long
#define debug(x) cout << #x << " = " << x << "\n"
void fastIO() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
int dir[4][2] = {{0, 1}, {-1, 0}, {1, 0}, {0, -1}};
void solve() {
int n, m;
cin >> n >> m;
char Map[n + 1][m + 1];
pair<int, int> start, end, fire;
char c;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> c;
Map[i][j] = c;
if (c == 'S')
start = {i, j};
else if (c == 'E')
end = {i, j};
else if (c == '*')
fire = {i, j};
}
}
queue<pair<pair<int, int>, int>> q;
q.push({start, 0});
Map[start.first][start.second] = '#';
Map[end.first][end.second] = '.';
Map[fire.first][fire.second] = '#';
bool find = false;
while (!q.empty()) {
int x = q.front().first.first;
int y = q.front().first.second;
int step = q.front().second;
q.pop();
if (x >= fire.first - step && x <= fire.first + step && y >= fire.second - step && y <= fire.second + step) {
if (x == end.first && y == end.second && (x == fire.first - step || x == fire.first + step || y == fire.second - step || y == fire.second + step)) // 极限情况
{
find = true;
cout << step << endl;
break;
} else
continue;
}
if (x == end.first && y == end.second) {
find = true;
cout << step << endl;
break;
}
for (int i = 0; i <= 3; i++) {
int xx = x + dir[i][0];
int yy = y + dir[i][1];
if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && Map[xx][yy] != '#') q.push(make_pair(make_pair(xx, yy), step + 1));
Map[xx][yy] = '#';
}
}
if (!find) cout << "T_T" << endl;
}
signed main() {
fastIO();
int t;
cin >> t;
while (t--) solve();
return 0;
}