92分求调

P2895 [USACO08FEB] Meteor Shower S

DougNo1 @ 2024-07-19 21:41:03

代码:

#include <bits/stdc++.h>
using namespace std;
struct point{
    int x,y;//坐标
    int t,step;//t:流星落下的时间  step:走到这里用的步数 
    bool b;//是否走过(0:没走过 1:走过) 
}a[1005][1005];
int main(){
    //输入n 结构体初始化 
    int n; 
    cin>>n;
    for(int i=1;i<=300;i++){
        for(int j=1;j<=300;j++){
            a[i][j].x = i;
            a[i][j].y = j;
            a[i][j].t = 1000;
            a[i][j].step = 100000;
            a[i][j].b = 0;
        }
    }
    //输入其他数据 做标记 
    int dx[6]={0,-1,1,0,0,0},dy[6]={0,0,0,-1,1,0};
    for(int i=1;i<=n;i++){
        int xx,yy,tt;
        cin>>xx>>yy>>tt;
        xx++,yy++;
        for(int j=1;j<=5;j++){
            int x1=xx+dx[j],y1=yy+dy[j];
            if(x1<1 || y1<1 || a[x1][y1].t<tt) continue;
            a[x1][y1].t=tt;
        }
    }

    //创建队列 队列初始化 
    queue<point> q;
    a[1][1].step=0;
    a[1][1].b=1;
    q.push(a[1][1]);
    //BFS 
    while(!q.empty()){
        point p=q.front();
        q.pop();

        for(int i=1;i<=4;i++){
            int xx=p.x+dx[i], yy=p.y+dy[i];
            if(xx<1 || yy<1 || xx>300 || yy>300 || a[xx][yy].b==1 || p.step+1>=a[xx][yy].t) continue;

            if(a[xx][yy].t == 1000){
                cout<<p.step+1;
                return 0;
            }

            a[xx][yy].x=xx;
            a[xx][yy].y=yy;
            a[xx][yy].b=1;
            a[xx][yy].step=p.step+1;
            q.push(a[xx][yy]);
        }
    }
    cout<<-1;
    return 0;
}

提交记录

请大佬们帮帮我!


|