renhongtu @ 2023-12-06 19:53:22
#include<bits/stdc++.h>
using namespace std;
bool vis[305][305];
int m;
int fuzhu[305][305]={0};
typedef struct sss{
int x,y,t;
}sss;
int d[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
sss star[50005];
typedef struct ren{
int rx,ry;
}ren;//贝茜
ren b;
bool compare(sss s1,sss s2){
return s1.t<s2.t;
}
void bfs(int sx, int sy, int tt) {
queue<ren> q;
q.push({sx, sy});
vis[sx][sy] = true; // 初始位置已访问
int step = 1;
while (!q.empty()) {
int size = q.size(); // 当前层的节点数量
// 更新星星爆炸影响的区域
while (step <= m && star[step].t == tt) {
for (int k = 0; k < 4; ++k) {
int nx = star[step].x + d[k][0];
int ny = star[step].y + d[k][1];
if (nx >= 0 && nx <= 300 && ny >= 0 && ny <= 300) {
vis[nx][ny]=true;
}
}
vis[star[step].x][star[step].y]=true;
// 爆炸点本身也是危险的
step++;
}
for (int i = 0; i < size; ++i) { // 遍历当前层的所有节点
ren c = q.front(); q.pop();
// 如果当前位置是安全的,输出答案并返回
if (fuzhu[c.rx][c.ry] == 0) {
cout << tt << endl;
return;
}
// 尝试四个方向移动
for (int j = 0; j < 4; ++j) {
int dx = c.rx + d[j][0];
int dy = c.ry + d[j][1];
if (dx >= 0 && dx <= 300 && dy >= 0 && dy <= 300 && !vis[dx][dy]) {
q.push({dx, dy});
vis[dx][dy] = true; // 标记为已访问
}
}
}
tt++; // 时间增加
}
// 如果队列为空,说明没有找到安全路径
cout << "-1" << endl;
}
int main(){
cin>>m;
for(int i=1;i<=m;++i){
cin>>star[i].x>>star[i].y>>star[i].t;
fuzhu[star[i].x][star[i].y]=1;
fuzhu[star[i].x-1][star[i].y]=1;//辅助数组为0的地方是永远安全的
fuzhu[star[i].x+1][star[i].y]=1;
fuzhu[star[i].x][star[i].y-1]=1;
fuzhu[star[i].x][star[i].y+1]=1;
}
sort(star+1,star+1+m,compare);
bfs(0,0,0);
return 0;
}
by renhongtu @ 2023-12-06 19:53:52
求指正
by 13288917088c @ 2023-12-25 13:11:02
1, 建议建一个int数组,存储该点被砸中的最短时间,因为流星是在逃离过程中砸下来的,如果在走到该点时(或之前),该点已经烧焦了,则直接continue。
2, 在到达其他点时提前判断是否永远安全,或者已经毁灭,优化内存(我就因为这点MLE了)
自己改代码,我的就不打出来了。
by 13288917088c @ 2023-12-25 13:11:36
@renhongtu
by 13288917088c @ 2023-12-25 13:13:34
虽然我很弱,但可以看一下
by 13288917088c @ 2023-12-25 13:14:21
给个关注QWQ
by 13288917088c @ 2023-12-25 13:16:15
好吧,我俩好像差不多(刚刚看了你的数据)
by 13288917088c @ 2023-12-25 13:22:31
我是学生党,可能不能及时回复