服装网站建设建议,dedecms网站二次开发,一款app是如何制作出来的,舟山seo思路#xff1a;BFS
这是一道BFS的题母庸质疑#xff0c;其实质上是一个迷宫问题。但是#xff0c;又与迷宫问题有不同的地方#xff0c;因为这里有干扰因素#xff0c;所以我们说这种问题就是有限制条件的迷宫问题。
BFS的照常遍历是没有问题。在题目中我们还需要考虑这…思路BFS
这是一道BFS的题母庸质疑其实质上是一个迷宫问题。但是又与迷宫问题有不同的地方因为这里有干扰因素所以我们说这种问题就是有限制条件的迷宫问题。
BFS的照常遍历是没有问题。在题目中我们还需要考虑这个人会不会被陨石砸到。这里在BFS中就需要特殊判断一下也就是看看陨石降落的时候这个人是在那个位置。如果说这个人走到这个位置的时候时刻大于陨石降落的时刻我们就应该舍弃掉这种可能性否则我们就可以走。
另外在陨石降落的时候可能是多颗所以在陨石降落的时候可能会烧到同一个地方所以我们需要取其中最早砸到地面的陨石的时间这一点很重要。
另外在人行走的限制条件时为什么没有规定最大上限呢你可以定但是没必要因为我们在遍历到安全的地方就不会走了所以无所谓。
还有在初始化陨石的数组时代码中fire就是代表陨石在这个坐标降落的时刻需要初始化为无穷大因为这样才能代表陨石不会降落到这个点上然后我们再去更新数值这样才是科学的。
上代码
#includeiostream
#includestdio.h
#includecstring
#includecstdlib
#includecmath
#includevector
#includealgorithm
#includestack
#includequeue
#include iomanip
#includesstream
#includenumeric
#includemap
#includelimits.h
#includeset
#define int long long
#define MAX 1010
#define _for(i,a,b) for(int ia;i(b);i)
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef pairint, int PII;
int n, m;
int countsINT_MAX;
int a, b;
int dx[] { -1,1,0,0 };
int dy[] { 0,0,-1,1 };
queuePIIq;
int res 0;
char maps[MAX][MAX];
int dist[MAX][MAX];
int fire[MAX][MAX];
int bfs() {q.push({ 0,0 });dist[0][0] 0;while (!q.empty()) {auto tmp q.front();q.pop();for (int i 0; i 4; i) {int a tmp.first dx[i];int b tmp.second dy[i];if (a 0 || b 0)continue;if (dist[a][b])continue;if (dist[tmp.first][tmp.second]1 fire[a][b])continue;dist[a][b] dist[tmp.first][tmp.second] 1;q.push({ a,b });if (fire[a][b]1e9)return dist[a][b];}}return -1;
}
signed main() {ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);cin n;memset(fire, 0x3f, sizeof fire);while (n--) {int x, y, t;cin x y t;fire[x][y] min(fire[x][y], t);for (int i 0; i 4; i) {int a dx[i] x;int b dy[i] y;if (a 0 || a301 || b 0 || b301)continue;fire[a][b] min(fire[a][b], t);}}int res bfs();cout res;return 0;
}
