救救孩子!!

P2895 [USACO08FEB] Meteor Shower S

Zero_Legend @ 2020-07-23 21:08:36

#include<bits/stdc++.h>
using namespace std;
int x,y;
int n;
int v[1000][1000];
int t[1000][1000];
int flag=0;
int ju=0;
const int N=0x3f;
queue <int> x1n;
queue <int> y1n;

void bfs()
{
    while(!x1n.empty()&&!y1n.empty())
    {
    flag++;//步数 
    if(t[x1n.front()][y1n.front()]==N)//到了安全的地方 
    {
        cout<<flag;
        ju++;//判断逃不逃的出去 
        return ;
    }
    if(flag<t[x1n.front()+1][y1n.front()])//向下 
    {
        x1n.push(x1n.front()+1);
        y1n.push(y1n.front());
    }
    if(flag<t[x1n.front()-1][y1n.front()]&&x1n.front()-1>=0)//向上 
    {
        x1n.push(x1n.front()-1);
        y1n.push(y1n.front());
    }
    if(flag<t[x1n.front()][y1n.front()+1])//向右 
    {
        x1n.push(x1n.front());
        y1n.push(y1n.front()+1);
    }
    if(flag<t[x1n.front()][y1n.front()-1]&&y1n.front()-1>=0)//向左 
    {
        x1n.push(x1n.front());
        y1n.push(y1n.front()-1);
    }
    //cout<<x1n.front()<<" "<<y1n.front()<<endl;
    x1n.pop();
    y1n.pop();//进入下一次的搜索 
    }
}

int main()
{
    memset(t,N,sizeof(t));
    cin>>n;
    x1n.push(0);
    y1n.push(0);
    for(int i=1;i<=n;i++)
    {
        cin>>x>>y;
        cin>>t[x][y];
        //cout<<x<<" "<<y<<" "<<t[x][y]<<endl;
        v[x][y]=1;
        if(x>=1) {
            v[x-1][y]=1; 
            t[x-1][y]=min(t[x][y],t[x-1][y]);
            //cout<<"x-1: "<<x-1<<"   y:  "<<y<<"  t[x-1][y]: "<<t[x-1][y]<<endl;
            //cout<<t[x][y]<<"   "<<t[x-1][y]<<endl<<endl;
        }

        v[x+1][y]=1; 
        t[x+1][y]=min(t[x][y],t[x+1][y]);

        if(y>=1) {
            v[x][y-1]=1; 
            t[x][y-1]=min(t[x][y],t[x][y-1]);
            //cout<<"x: "<<x<<"   y-1:  "<<y-1<<"  t[x][y-1]: "<<t[x][y-1]<<endl;

        }

        v[x][y+1]=1; 
        t[x][y+1]=min(t[x][y],t[x][y+1]);
        //v判断陨石在没在过,t判断陨石掉的时间 

    //  for(int i=0;i<=5;i++)
    //{
    //  for(int j=0;j<=5;j++)
    //  {
    //      cout<<t[i][j]<<" "; 
    //  }
    //  cout<<endl;
    //}
    }
    bfs();
    if(ju==0) cout<<-1;//走不到 
    return 0;
}

样例都过不了,找不到错


by WanderingTrader @ 2020-07-23 21:24:11

用户名好评


by stdout @ 2020-07-23 21:29:46

用户名好评


by 奥特战士 @ 2020-07-24 09:44:07

用户名好评


|