[数据结构与算法]【洛谷题解】-P2895【USACO08FEB】Meteor Shower S

题目概况

题目链接： https://www.luogu.com.cn/problem/P2895
难度： 普及/提高-

题目分析

简化题目： 有若干颗流星随时坠落，你需要在最短时间内找到一个永远不会坠落流星的地方
涉及知识点： 广度优先搜索BFS及其状态表示的技巧
解题思路：
明显，这是一道广搜题，最难处理的点应该是时间。
我们每次流星坠落，当前坐标及其上、下、左、右四个方向都会被摧毁，定义为“受流星摧毁”。
我们可以用一个数组来记录当前格子受流星摧毁的首次时间，从上、下、左、右四个方向搜索，在第一象限内、是未走过的坐标、是在受流星摧毁时刻前到达的，只要满足这三个条件即可加入队列。如果当前坐标的受流星摧毁的首次时间为无穷大（0x3f3f3f3f），那么就说明找到了！找不到就输出-1.

代码拆解及要点解析

一、数据准备

int m; //m颗流星
bool vis[400][400]; //标记走没走过
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; //四个方向
int comefirst[400][400]; //流星第一次来的时间 
struct node {
	int x;
	int y;
	int t; //当前的横纵坐标处，时刻 
	node (int _x, int _y, int _t) { //结构体构造函数
		x = _x;
		y = _y;
		t = _t;
	}
};
queue <node> q; //广搜用的好东西

二、输入并预处理受流星摧毁的首次时间

清一色的，我们采用min函数更新即可

	for (int i = 1; i <= m; i++) {
		int x, y, t;
		cin >> x >> y >> t;
		comefirst[x][y] = min(comefirst[x][y], t);
		for (int j = 0; j < 4; j++) {
			int tx = x + dir[j][0];
			int ty = y + dir[j][1];
			if (in(tx, ty)) {
				comefirst[tx][ty] = min(comefirst[tx][ty], t);
			}
		}
	}

三、广搜核心代码

记住，如果你的结构体内有构造函数，你必须用构造函数先构造

我们只需要按上文照解题思路里面的三个判断来执行就好了

		for (int i = 0; i < 4; i++) {
			node v = node(0, 0, 0);
			v.x = now.x + dir[i][0];
			v.y = now.y + dir[i][1];
			v.t = now.t + 1;
			if (in(v.x, v.y) && !vis[v.x][v.y] && v.t < comefirst[v.x][v.y]) {
				q.push(v);
				vis[v.x][v.y] = true; 
				if (comefirst[v.x][v.y] == 0x3f3f3f3f) {
					return now.t + 1;
				}
			}
		} 

完整代码

还有一些小细节我写在注释里了~

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

int m; //m颗流星
bool vis[400][400];
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int comefirst[400][400]; //流星第一次来的时间 
struct node {
	int x;
	int y;
	int t; //当前的横纵坐标处，时刻 
	node (int _x, int _y, int _t) {
		x = _x;
		y = _y;
		t = _t;
	}
};
queue <node> q;

bool in(int a, int b) {
	return a >= 0 && b >= 0 && a <= 399 && b <= 399; 
	//其实<=你也可以不加，加了速度会更快，而且防止一些奇怪的问题
}

int bfs() {
	q.push(node(0, 0, 0));
	vis[0][0] = true;
	while (!q.empty()) {
		node now = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			node v = node(0, 0, 0);
			v.x = now.x + dir[i][0];
			v.y = now.y + dir[i][1];
			v.t = now.t + 1;
			if (in(v.x, v.y) && !vis[v.x][v.y] && v.t < comefirst[v.x][v.y]) {
				q.push(v);
				vis[v.x][v.y] = true; 
				if (comefirst[v.x][v.y] == 0x3f3f3f3f) {
					return now.t + 1;
				}
			}
		} 
	}
	return -1;
}
int main() {
	cin >> m;
	memset(comefirst, 0x3f, sizeof(comefirst));
	for (int i = 1; i <= m; i++) {
		int x, y, t;
		cin >> x >> y >> t;
		comefirst[x][y] = min(comefirst[x][y], t);
		for (int j = 0; j < 4; j++) {
			int tx = x + dir[j][0];
			int ty = y + dir[j][1];
			if (in(tx, ty)) {
				comefirst[tx][ty] = min(comefirst[tx][ty], t);
			}
		}
	}
	cout << bfs() << endl;
	return 0;
}