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
全初始化成
其次 v[u][V]=w;
v[u+1][V]=w;
这里你没有跟原来的值取
然后 if(tx<0||ty<0||tx>=300||ty>=300)continue;
这里应该是 tx<0||ty<0||tx>301||ty>301
因为奶牛有权走到下标
同时 if(vis[tx][ty]||v[tx][ty]<=now.step)continue;
这一句中应该是 v[tx][ty]<=now.step+1
并且你没有判
最后是你过不去样例的原因:
你的代码中 v[tx][ty]<=now.step
就会被 continue
,并且你把 v
初始化成 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 谢谢(迟来的感谢)