题目描述
blablabla
样例
#include<iostream>
#include <queue>
#include<cstring>
using namespace std;
int T, R, C;
int dis[205][205];
char a[205][205];
int ans;
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
void bfs(pair<int, int> start)
{
queue < pair<int, int>> q;
pair<int, int> u;
q.push(start);
while (!q.empty())
{
u = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
if (u.first + dx[i] >= 0 && u.first + dx[i] < R && u.second + dy[i] >= 0 &&
u.second + dy[i] < C && a[u.first + dx[i]][u.second + dy[i]] == '.')
{
q.push({ u.first + dx[i],u.second + dy[i] });
dis[u.first + dx[i]][u.second + dy[i]] = dis[u.first][u.second] + 1;
a[u.first + dx[i]][u.second + dy[i]] = '#';
}
else if (u.first + dx[i] >= 0 && u.first + dx[i] < R && u.second + dy[i] >= 0 &&
u.second + dy[i] < C && a[u.first + dx[i]][u.second + dy[i]] == 'E')
{
cout << dis[u.first][u.second] + 1<<endl;
return;
}
else
continue;
}
}
cout << "oop!"<<endl;
return;
}
int main()
{
cin >> T;
while (T--)
{
pair<int, int> u;
cin >> R >> C;
memset(dis, 0, sizeof(dis));//每次输入数据后,要将dis置为0,
//否则在BFS()函数中会用到上一组的dis数据,导致出错。
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
cin >> a[i][j];
if (a[i][j] == 'S')
u.first = i, u.second = j;
}
}
bfs(u);
}
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla