tyx20101117 @ 2022-11-27 11:33:17
#include<bits/stdc++.h>
using namespace std;
char v[605][605][1005];//v[x][y][t]表示第t个时间单位(x,y)的情况
int f[605][605];//f[x][y]表示到达(x,y)需要多少个时间单位
struct node{
int x,y,t;//x,y是陨石砸下的坐标,t是陨石在第几个时间单位砸下来
};
node a[500005];
void copy(int time){
int i,j;
for (i=1;i<=600;i++){
for (j=1;j<=600;j++){
v[i][j][time+1]=v[i][j][time];
}
}//时间流逝一个单位
for (i=1;i<=600;i++){
for (j=1;j<=600;j++){
if (v[i][j][time]='@'){
if (v[i+1][j][time+1]=='.'){
v[i+1][j][time+1]='@';
f[i+1][j]=f[i][j]+1;
}
if (v[i-1][j][time+1]=='.'){
v[i-1][j][time+1]='@';
f[i-1][j]=f[i][j]+1;
}
if (v[i][j+1][time+1]=='.'){
v[i][j+1][time+1]='@';
f[i][j+1]=f[i][j]+1;
}
if (v[i][j-1][time+1]=='.'){
v[i][j-1][time+1]='@';
f[i][j-1]=f[i][j]+1;
}
}
}
}//标记Bessie现在所等到达的所有地点和到达要用的时间
}//时间流逝
bool cmp(node aa,node bb){
return (aa.t<bb.t);
}
int main(){
int i,j,k,n;
{
for (i=0;i<=600;i++){
for (j=0;j<=600;j++){
v[i][j][0];
}
}
v[0][0][0]='@';//Bessie一开始在(0,0)
}//初始化
{
cin>>n;
for (i=1;i<=n;i++){
cin>>a[i].x>>a[i].y>>a[i].t;
}
sort(a+1,a+n+1,cmp);//按砸下的时间给陨石排序
}
{
//k表示当前时间
//time表示下一枚陨石砸下的时间
//ans表示砸到了第几颗陨石
int time,ans;
ans=1;
for (k=0;k<=1000;k++){
time=a[ans].t;
while (time==k){
v[a[ans].x+0][a[ans].y+0][k]='#';
v[a[ans].x+1][a[ans].y+0][k]='#';
v[a[ans].x-1][a[ans].y-0][k]='#';
v[a[ans].x+0][a[ans].y+1][k]='#';
v[a[ans].x-0][a[ans].y-1][k]='#';//标记陨石能影响到的5个点
time=a[++ans].t;
}
copy(k);//如果第k个时间单位的陨石砸完了,时间就流逝一个单位
}
}
{
int ans;
ans=1005;//ans表示最少时间
for (i=1;i<=600;i++){
for (j=1;j<=600;j++){
if (v[i][j][1000]=='@'){
ans=min(ans,f[i][j]);
}//如果陨石砸完后仍是安全地点,就判断到达这个点的时间
}
}
cout<<ans;
}
return 0;
}
MLE,哪位大佬可以帮忙优化下空间……
by kkksc004 @ 2022-12-04 16:44:41
?