有没有大佬检查一下本蒟蒻的WA代码……

P2895 [USACO08FEB] Meteor Shower S

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

?


|