萌新一直过不去 求助

P2895 [USACO08FEB] Meteor Shower S

Liyuqiao11 @ 2023-01-12 18:03:26

#include<bits/stdc++.h>
using namespace std;
long long int m,vis[1010][1010],dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},a[1010][1010];
struct N{
    int cnt;
    int x;
    int y;
};
int bfs(int x,int y){
    queue<N> q;
    q.push((N){0,x,y});
    vis[x][y]=1;
    while(!q.empty()){
        int u=q.front().x,v=q.front().y,dc=q.front().cnt;
        q.pop();
        for(int i=0;i<4;i++){
            int nx=u+dx[i],ny=v+dy[i];
            if(nx>=0&&ny>=0&&vis[nx][ny]==0&&(a[nx][ny]>dc+1||a[nx][ny]==-1)){
                if(a[nx][ny]==-1){
                    return dc+1;
                }
                q.push((N){dc+1,nx,ny});
                vis[nx][ny]=1;
            }
        }
    }
    return -1;
}
int main(){
    cin>>m;
    memset(a,-1,sizeof(a));
    for(int i=1;i<=m;i++){
        long long int d,c,yq;
        cin>>d>>c;
        cin>>yq;
        if(a[d][c]==-1){
            a[d][c]=yq;
        }
        else{
            a[d][c]=min(a[d][c],yq);
        }
        if(a[d+1][c]==-1){
            a[d+1][c]=a[d][c];
        }
        else{
            a[d+1][c]=min(a[d+1][c],a[d][c]);   
        }
        if(a[d][c+1]==-1){
            a[d][c+1]=a[d][c];
        }
        else{
            a[d][c+1]=min(a[d][c+1],a[d][c]);   
        }
        if(d>=1){
            if(a[d-1][c]==-1){
                a[d-1][c]=a[d][c];
            }
            else{
                a[d-1][c]=min(a[d-1][c],a[d][c]);
            }
        }
        if(c>=1){
            if(a[d][c-1]==-1){
                a[d][c-1]=a[d][c];
            }
            else{
                a[d][c-1]=min(a[d][c-1],a[d][c]);
            }
        }
    }
    cout<<bfs(0,0);
    return 0;
}

by Liyuqiao11 @ 2023-01-12 18:42:29

此贴结


|