BFS
我个人理解:
BFS 先把初始状态入队,然后进入循环,1.弹出队头 2.拓展队头的子节点( 判个重) ,然后压入队尾
from y总~
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#define x first
#define y second
using namespace std;
const int N = 210;
typedef pair<int, int> PII;
int n, m;
char g[N][N];
int dist[N][N]; // 把判重和距离数组合为一个
int bfs(PII start, PII end) // 注意 start end都是PII类型的 别写错了
{
queue<PII> q;
memset(dist, -1, sizeof dist); // 把距离数组都初始化成-1
dist[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())
{
PII t = q.front();
// 弹出队头
q.pop();
for (int i = 0; i < 4; i ++ )
{
int a = t.x + dx[i], b = t.y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m) continue; // 出界,跳出本次循环
if (dist[a][b] != -1) continue; // 走过了,跳出本次循环
if (g[a][b] == '#') continue; // 撞到障碍物
dist[a][b] = dist[t.x][t.y] + 1;
if (end == make_pair(a, b)) return dist[a][b]; // 走到终点了,返回距离
q.push({a, b});
}
}
return -1;
}
int main()
{
int T;
cin >> 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) printf("oop!\n");
else printf("%d\n", distance);
}
return 0;
}
为啥不能一个一个读入,边读入边判断起点和终点呢?
while(n–){
我这样就报错,但是换成换行读入就行了,看了好久
可能有回车?%s不会这样
哦!应该是!谢谢!!
😁
换成cin 应该可以
为什么会这个样子啊?想好久了
大佬,最后的end==make_pair是什么意思
end是PII类型,make_pair把a,b合成PII类型来比较是否到达终点
萌新 咨询一下这个数组的输入可以吗?为什么要用一维输入啊?我的理解是这样的:按行输入,按行处理?
字符串可以一行一行的输入
为什么bfs的三个if不能合并成一个if判断呀
个人感觉不是同一类的if判断还是分开写可能会更清晰些
可以合在一起判断是没有错的
这个是不是不用把dist初始化也可以啊= =。
因为同一个位置有可能被访问两次,所以最好初始化一下,当然你也可以用另外一个数组来表示是否被访问