求助!71分BFS!

P2895 [USACO08FEB] Meteor Shower S

Lyrith_with_xQ @ 2023-08-30 11:47:34

#include <bits/stdc++.h>
using namespace std;

struct node
{
    int x,y,s;
};

queue<node> q;
int n,x,y,t,mp[301][301],nxt[4][2]={{1,0},{-1,0},{0,1},{0,-1}},ans=1e9;
bool vis[301][301];

bool in_area(int x,int y)
{
    return (x>=0&&x<301&&y>=0&&y<301);
}

void bfs()
{
    vis[0][0]=true;
    q.push({0,0,0});
    while(!q.empty())
    {
        node a=q.front();
        q.pop();
        if(mp[a.x][a.y]==-1)ans=min(ans,a.s);
        else if(mp[a.x][a.y]<=a.s)continue;
        for(int i=0;i<4;i++)
        {
            int nx=a.x+nxt[i][0],ny=a.y+nxt[i][1];
            if(!in_area(nx,ny)||vis[nx][ny])continue;
            vis[nx][ny]=true;
            q.push({nx,ny,a.s+1});
        }
    }
}

int main()
{
    memset(mp,-1,sizeof(mp));
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>x>>y>>t;
        mp[x][y]=t;
        for(int j=0;j<4;j++)
        {
            if(!in_area(x+nxt[j][0],y+nxt[j][1]))continue;
            if(mp[x+nxt[j][0]][y+nxt[j][1]]!=-1)mp[x+nxt[j][0]][y+nxt[j][1]]=min(t,mp[x+nxt[j][0]][y+nxt[j][1]]);
            else mp[x+nxt[j][0]][y+nxt[j][1]]=t;
        }
    }
    bfs();
    if(ans!=1e9)cout<<ans;
    else cout<<"-1";
    return 0;
} 

大小细节差不多都考虑到了,却71分,哪里错了?


by chen227 @ 2023-10-02 14:58:08

遇到怎么找也找不出的问题,可以重新写一遍代码(不要记原来的代码),说不定就可以了


|