#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue> // 队列 --- bfs,最短的步数
#define x first
#define y second
using namespace std;
const int N = 210;
typedef pair<int, int> PII; // 存下每个点的横纵坐标
char g[N][N];
int dist[N][N];
int n, m;
/*
bfs的实质:
依次遍历距离起点为0,为1,为2,为3... 的点,如果在某一层满足条件,必然是最短距离(因为有判重数组dist[][],同时也是距离数组)
依靠队列来确保实现一层一层的遍历
bfs操作的具体步骤:
1.定义队列q,起点的距离初始化为0
2.while(队列非空)
1)取出队首元素 front()
2)pop() 弹出队首
3) 查找4个方向,根据条件筛选,
如果是end结束,
否则用已知点更新当前点距离dist[x][y] = dist[t.x][t.y]+1
4) 最后将正常的点放入队列中- push()尾插
需要注意:
1.使用到了pair, 记录每个点的横纵坐标
2.使用到memset(dist -1),距离预设初值-1
3.使用到了make_pair,构造一个pair
*/
int bfs(PII start, PII end)
{
queue<PII> q; // 构造队列
memset(dist, -1, sizeof dist); // 将dist[][]初始化为-1
//初始化起点到起点的距离:0,
dist[start.x][start.y] = 0;
q.push(start); //队尾插入
//构建向量
int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
while (q.size()) //队列非空
{
auto t = q.front(); //队首元素
q.pop(); //队头弹出
for (int i = 0; i < 4; i++)
{
int x = t.x + dx[i], y = t.y + dy[i];
if (x<0 || x >= n || y<0 || y>= m) continue; // 出界
if (g[x][y] == '#') continue; // 障碍物
if (dist[x][y] != -1) continue; // 之前已经遍历过
dist[x][y] = dist[t.x][t.y] + 1;
if (end == make_pair(x, y)) return dist[x][y];
q.push({ x,y });
}
}
return -1;
}
void solve()
{
cin >> n >> m;
//读入
for (int i = 0; i < n; i++)
cin >> g[i];
//找到start,end
PII start, end;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (g[i][j] == 'S') start = { i,j };
else if (g[i][j] == 'E') end = { i,j };
//bfs
int distance = bfs(start, end);
if (distance == -1) cout << "oop!\n";
else cout << distance << '\n';
}
int main()
{
int t;
cin >> t;
while (t--)
solve();
return 0;
}