洛谷 / 题目列表 / 题目详情 P2895[USACO08FEB]Meteor Shower S

BFS
测试数据不能比0小，但是可以比300大

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define MAXN 310
using namespace std;

struct Node{
	int x, y;
	Node(int x, int y){
		this->x = x;
		this->y = y;
	}
	Node(){
	}
};
queue<Node> q;
int dx[] = {0, -1, 1, 0 , 0, },
	dy[] = {0, 0, 0, -1, 1, };
int g[MAXN][MAXN] // g[x][y] = 储存最早落下来的流星的时间, 初始化全-1
	, ans[MAXN][MAXN] //ans[x][y] = 走到(x, y)点处的时间
	, vis[MAXN][MAXN];
int m;

int main(){
	
	memset(g, -1, sizeof(g));
	scanf("%d", &m);
	for(int i=0; i<m; i++){
		int x, y, t, xx, yy;
		scanf("%d%d%d", &x, &y, &t);
		
		for(int i=0; i<5; i++){
			xx = x + dx[i];
			yy = y + dy[i];
			
			if(xx >= 0 && yy >= 0 && (g[xx][yy] == -1 || g[xx][yy] > t)){
			/* 如果(x,y)处没有流星落下或者g[x][y]的时间比现在这个流星的时间晚, 
			则更新g[x][y]的值,保证g[x][y]内是最早落下来的流星的时间*/
				g[xx][yy] = t;
			}
		}
	}
	// 从(0, 0)出发
	vis[0][0] = 1;
	q.push(Node(0, 0));
	
	while(!q.empty()){
		
		Node node = q.front();
		q.pop();
		
		int x = node.x,	
			y = node.y,
			t;
		//更新时间
		t = ans[x][y] + 1;
		//找到安全格子，输出t-1为路上花费
		if(g[x][y] == -1){
			printf("%d", t-1);
			return 0;
		}
		// 搜索
		for(int i=1; i<5; i++){
			int xx = x + dx[i],
				yy = y + dy[i];
			
			if(xx >= 0 && yy >= 0 && (g[xx][yy] == -1 ? 1 : t < g[xx][yy]) && !vis[xx][yy]){
			/*
			如果g[x][y] == -1， 则为安全格可以进入, 
			或者t比g[xx][yy]处流星落下的时间早, 也可以进入
			*/
				vis[xx][yy] = 1;
				ans[xx][yy] = t;
				q.push(Node(xx, yy));
			}
			
		}
		
	}
	printf("-1");
	return 0;
}