求调!

P2895 [USACO08FEB] Meteor Shower S

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 嗯哼,自个加油!


|