7分。。求调

P2895 [USACO08FEB] Meteor Shower S

godogod @ 2024-08-24 17:40:42


#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=nx+dx[i];
            int yy=ny+dy[i];
            if(map_[xx][yy]==true && xx>=0 && yy>=0 && rockfall(xx,yy) )
            {
                time_++;
                tail++;
                que[tail].x=xx;
                que[tail].y=yy;
//              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-08-24 18:16:46

好家伙,最近一直在做 bfs 的专题吗?!


by szrgjxms @ 2024-08-24 18:21:21

题目说是要到一个安全的格子里面,说明之后会被流星砸中的格子都不会是安全的格子里,你可以给这些流星会砸中的格子打上标记,之后走到一些格子之后判断一下是否在这些会被砸中的格子里就可以了。 @godogod


by godogod @ 2024-08-25 11:07:33

@szrgjxms 我试试


|