题目描述
blablabla
样例
#include<bits/stdc++.h>
#define endl "\n"
#define INF 0x3f3f3f3f3f3f
using namespace std;
const int N=210; //注意多存几个,防止数组溢出
int n,m;
char map[N][N]; //存储地图 ,注意是字符数组
//dx与dy代表移动的方向向量 ,上下左右
int dx[4]={-1,1,0,0};//不能写成 dx={-1,1,0,0};
int dy[4]={0,0,-1,1};
// 把判重和距离数组合为一个,判断是否经过,并且储存长度
int dist[N][N];
//涉及到平面坐标的时候,使用pair,储存x与y坐标
//涉及三个及以上个值,使用结构体struct
#define x first //x代替pair中的first
#define y second
typedef pair<int, int> PII; //这里使用typedef //用来储存一个点的x和y坐标
bfs(PII start,PII end)
{
//bfs使用队列,先进先出,依次把每一层的数据投入队列中
queue<PII> q;
memset(dist, -1, sizeof dist); // 把距离数组都初始化成-1,-1也代表没有遍历过
dist[start.x][start.y] = 0; // 起点开始,距离为0,且已经遍历
q.push(start); // 起点 入队
while(q.size()) //当队列不为0
{
PII t = q.front();//取队头元素 ,作为当前点
// 弹出队头,便于下一次循环
q.pop();
for (int i = 0; i < 4; i ++ ) //对这个点,进行四个方向上的遍历
{
int a = t.x + dx[i], b = t.y + dy[i]; //记录可能成为下一个起点的x与y坐标
if (a < 0 || a >= n || b < 0 || b >= m) continue; // 出界,跳出本次循环
if (dist[a][b] != -1) continue; // 走过了,跳出本次循环
if (map[a][b] == '#') continue; // 撞到障碍物
//如果满足前行要求,则走到下一个点,并且此时走到该点经过的路径是:走到上一个点经过的路径加一
dist[a][b] = dist[t.x][t.y] + 1;
//用a,b的值创造一个pair类型变量(因为end是pair类型),若与end相等,则走到终点,返回经过的路径
if (end == make_pair(a, b)) return dist[a][b]; // 走到终点了,返回距离
//若没有到终点,则继续循环下一个点,并且把当前点放入队列中
q.push({a, b});//把查询到的点,加入队列中
}
}
return -1;
}
signed main()
{
int t;
cin>> t;
while(t--)
/*因为一次有t组数据,所以几乎所有的操作都要在while循环中进行
(包括某些变量的定义以及bfs函数)
当本次结果得出后,进行下一次循环 */
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>map[i]; //map是二维数组,这种输入可以看作一次性输入一整行 ,只循环一重
}
//定义起点与终点
PII start, end;
//检测起点与终点,并存储起来
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
if (map[i][j] == 'S') start = {i, j};
else if (map[i][j] == 'E') end = {i, j};
int distance = bfs(start, end);
if (distance == -1) printf("oop!\n");
else printf("%d\n", distance);
}
return 0;//一定要写!!!
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla