题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 210;
int n, m;
char g[N][N];
int d[N][N];
int bfs(PII start, PII end)
{
queue<PII> q;//队列
memset(d, -1, sizeof d);//将距离初始化为-1
d[start.x][start.y] = 0;//起点的距离为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 || g[x][y] == '#' || d[x][y] != -1) continue;//出界 或者不能走 或者 已走过
//如果可以走,更新距离
d[x][y] = d[t.x][t.y] + 1;
if(end == make_pair(x, y)) return d[x][y];//返回到终点的距离
q.push({x, y});
}
}
return -1;
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d%d", &n, &m);
for(int i = 0; i <n; i++) scanf("%s", g[i]);
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};
int distance = bfs(start, end);
if(distance == -1) puts("oop!");
else printf("%d\n",distance );
}
return 0;
}