92分求调

P2895 [USACO08FEB] Meteor Shower S

Psy_Chen @ 2024-11-14 16:52:56

#include <bits/stdc++.h>
#define MAXNUM 305
#define INF 0x7fffffff
using namespace std;
unsigned int mapm[MAXNUM][MAXNUM]={0};
unsigned int step[MAXNUM][MAXNUM]={0};
bool vis[MAXNUM][MAXNUM]={false};
int dx[5]={0,0,1,0,-1};
int dy[5]={0,1,0,-1,0};
queue<pair<int,int>> q;

int main(){
    freopen("P2895_14.in","r",stdin);
    unsigned int M,need=1001;
    bool canvis=false;
    for(int x=0;x<=300;x++){
        for(int y=0;y<=300;y++){
            mapm[x][y]=1001;
            step[x][y]=INF;
        }
    }
    cin>>M;
    for(int i=1;i<=M;i++){
        unsigned int x,y,t;
        cin>>x>>y>>t;
        for(int j=0;j<5;j++)
        {
            if(x+dx[j]>=0&&x+dx[j]<=300
            && y+dy[j]>=0&&y+dy[j]<=300)
            mapm[x+dx[j]][y+dy[j]]=min(mapm[x+dx[j]][y+dy[j]],t);
        }
    }
    q.push(pair(0,0));
    step[0][0]=0;
    while(!q.empty()){
        int nx=q.front().first,ny=q.front().second;
        if(mapm[nx][ny]==1001||(nx>300||ny>300)){
            canvis=true;
            need=min(need,step[nx][ny]);
            q.pop();
            continue;
        }
        for(int i=1;i<5;i++){
            int st=step[nx][ny];
            int mx=nx+dx[i],my=ny+dy[i];
            if(mx>=0&&mx<=301
            && my>=0&&my<=301
            && vis[mx][my]==false
            && st+1<mapm[mx][my])
            {
                vis[mx][my]=true;
                q.push(pair(mx,my));
                step[mx][my]=st+1;
            }
        }
        q.pop();
    }
    if(canvis) cout<<need<<endl;
    else cout<<"-1"<<endl;
    return 0;   
}

百思不得解


by Psy_Chen @ 2024-11-14 16:55:26

悟了(( 越界的时候mapm没有赋值


|