求助

P2895 [USACO08FEB] Meteor Shower S

SunXiaoping @ 2021-10-21 19:30:09

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int x,y,step;
    node(int xx,int yy,int tep)
    {
        x=xx;
        y=yy;
        step=tep;
    }
};
int dx[10]={0,1,0,-1},dy[10]={1,0,-1,0},v[305][305],m,vis[305][305],ans=0x7fffffff;
queue<node> q;
inline void bfs()
{
    while(!q.empty())q.pop();
    q.push(node(0,0,0));
    vis[0][0]=1;
    while(!q.empty())
    {
        node now=q.front();
        q.pop();
        int x=now.x,y=now.y;
        if(!v[x][y])
        {
            ans=min(ans,now.step);
        }
        for(int i=0;i<4;i++)
        {
            int tx=x+dx[i],ty=y+dy[i];
            if(tx<0||ty<0||tx>=300||ty>=300)continue;
            if(vis[tx][ty]||v[tx][ty]<=now.step)continue;
            vis[tx][ty]=1;
            q.push(node(tx,ty,now.step+1));
        }
    }
}
int main()
{
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int u,V,w;
        cin>>u>>V>>w;
        v[u][V]=w;
        if(u-1>=0)
        if(!v[u-1][V])
        v[u-1][V]=w;
        else v[u-1][V]=min(v[u-1][V],w);
        v[u+1][V]=w;
        if(V-1>=0)
        if(!v[u][V-1])
        v[u][V-1]=w;
        else
        v[u][V-1]=min(v[u][V-1],w);
        if(!v[u][V+1])
        v[u][V+1]=w;
        else
        v[u][V+1]=min(v[u][V+1],w);
    }
    bfs();
    cout<<ans<<"\n";
}

by Rui_R @ 2021-10-21 20:48:20

@explpl2007 首先你不能将 v 全初始化成 0,因为陨石可能在 0 时刻落下

其次 v[u][V]=w; v[u+1][V]=w; 这里你没有跟原来的值取 \min

然后 if(tx<0||ty<0||tx>=300||ty>=300)continue;

这里应该是 tx<0||ty<0||tx>301||ty>301

因为奶牛有权走到下标 302 处,题目里只写了陨石的范围在 300 以内;再往外走没有意义。按你那样写最后一个点会有问题

同时 if(vis[tx][ty]||v[tx][ty]<=now.step)continue; 这一句中应该是 v[tx][ty]<=now.step+1

并且你没有判 -1

最后是你过不去样例的原因:

你的代码中 v[tx][ty]<=now.step 就会被 continue ,并且你把 v 初始化成 0,导致你永远走不到一个 v[tx][ty]=0 的点

一个建议,if(!v[x][y]){ans=min(ans,now.step);}

可以改成 if(!v[x][y]){ans=now.step;break;}

因为这里第一个搜到的满足条件的点一定是最优的;离终点更近的满足条件的点会比离终点更远的点先被搜到

其他可能还有,但大体应该就这些了

祝你好运。


by SunXiaoping @ 2021-10-28 15:31:05

@Rui_R 谢谢(迟来的感谢)


|