godogod @ 2024-10-04 15:48:48
#include<bits/stdc++.h>
using namespace std;
int m;
int nx[50002],ny[50002],t[50002];
bool map_[400][400];
int time_=0,last_time=0;
struct node
{
int x,y;
}que[1000005];
bool rockfall(int x,int y)
{
for(int i=1;i<=m;i++)
{
if(t[i]==time_+1)
{
map_[nx[i]][ny[i]]=false;
map_[nx[i]+1][ny[i]]=false;
map_[nx[i]-1][ny[i]]=false;
map_[nx[i]][ny[i]+1]=false;
map_[nx[i]][ny[i]-1]=false;
}
}
if(map_[x][y]==true)return true;
else return false;
}
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int head,tail;
bool bfs(int nx,int ny)
{
head=0;tail=1;
que[1].x=nx;
que[1].y=ny;
while(head<=tail)
{
head++;
for(int i=0;i<4;i++)
{
int xx=que[head].x+dx[i];
int yy=que[head].y+dy[i];
if(map_[xx][yy]==true && xx>=0 && yy>=0 && rockfall(xx,yy) )
{
time_++;
tail++;
que[tail].x=xx;
que[tail].y=yy;
map_[xx][yy]=false;
// cout<<xx<<" "<<yy<<endl;
if(time_>=last_time)
{
return true;
}
}
}
}
return false;
}
int main()
{
cin>>m;
memset(map_,true,sizeof(map_));
for(int i=1;i<=m;i++)
{
cin>>nx[i]>>ny[i]>>t[i];
last_time=t[i];
}
// cout<<last_time<<endl;
if(bfs(0,0))
{
cout<<time_;
return 0;
}
else cout<<-1;
return 0;
}
by szrgjxms @ 2024-10-04 18:57:57
emmm...先不说别的,你这复杂度有点大啊,给你提供一个思路,你可以直接用 map[][] 来记录流星砸到某个位置的时间(可以在输入的时候就直接初始化),然后再加一个 bz[] 来判断这个点是否走过(非常朴素的 bfs算法 啊)。然后你只要求走到最短距离到安全位置(就是map[][] = 0 的地方)就可以了。
by godogod @ 2024-10-05 14:33:51
@szrgjxms OK谢谢大佬
by szrgjxms @ 2024-10-05 14:48:49
@godogod 嗯哼,自个加油!