zhiyuan1020 @ 2024-05-25 10:38:11
#include <stdio.h>
#include <cmath>
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <cstring>
#include <stack>
#include <iomanip>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <cctype>
#include <cstdio>
#include <sstream>
#include <climits>
#include <unordered_set>
#include <utility>
#include <functional>
#include <iomanip>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
typedef long long ll;
int mi = INT_MAX, ma = -INT_MAX;
int m;
double mp[303][303] = { 0 };
bool vis[303][303] = { false };
struct now {
int x, y;
double t;
//定义结构体 目前位置坐标 时间
};
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,-1,0,1 };
bool check(now k) {//检查坐标合法性函数
if (k.x < 0 || k.y < 0)return false;
if (k.x > 300 || k.y > 300)return false;//要求在棋盘内
if (k.t >= mp[k.x][k.y])return false;//在流星波及之前到达此坐标
return true;
}
void bfs() {//广度优先搜索
queue<now>q;
now a;
a.x = 0, a.y = 0, a.t = 0;
vis[0][0] = true;
q.push(a);
now f, nex;
while (!q.empty()) {
f = q.front();
q.pop();//队列首位弹出
for (int i = 0;i < 4;i++) {
nex = f;//枚举f上下左右四个点
nex.x += dx[i];
nex.y += dy[i];
nex.t = f.t + 1;
if (nex.x >= 0 && nex.y >= 0 &&
mp[nex.x][nex.y] == 0) {
break;
}
if (vis[nex.x][nex.y])continue;
else vis[nex.x][nex.y] = true;
if (check(nex)) {//如果该点合法 入队
q.push(nex);
}
}
if (nex.x >= 0 && nex.y >= 0 &&
mp[nex.x][nex.y] == 0) {
break;
}
}
if (nex.x >= 0 && nex.y >= 0 &&
mp[nex.x][nex.y] == 0) {
cout << nex.t;
}
else cout << -1;
}
bool cover(int x, int y, double t) {//流星坠落时间覆盖函数
if (x < 0 || y < 0)return false;
if (x > 300 || y > 300)return false;//要求在棋盘内
if (mp[x][y] == 0)return true;//未被波及 可以覆盖
if (mp[x][y] > t)return true;//更早坠落 可以覆盖
return false;
}
int main(void) {
cin >> m;
int tmp, now, sum, ans, x, y;
double tim;
for (int i = 1;i <= m;i++) {
cin >> x >> y >> tim;
if (tim == 0)tim = 0.5;
if (cover(x, y, tim))mp[x][y] = tim;//该点是否覆盖
for (int j = 0;j < 4;j++) {//该点周围是否覆盖
if (cover(x + dx[j], y + dy[j], tim)) {
mp[x + dx[j]][y + dy[j]] = tim;
}
}
}//初始在地图上打印m个流星的时间
bfs();
return 0;
}