BZOJ 1671: [Usaco2005 Dec]Knights of Ni 骑士 (bfs)

题目:

  https://www.lydsy.com/JudgeOnline/problem.php?id=1671

题解:
  按题意分别从贝茜和骑士bfs然后meet_in_middle。。

  把一个逗号打成分号调了20分钟。。。

代码:

 #include<bits/stdc++.h>

 using namespace std;

 const int mx[]={,-,,,},my[]={,,,-,};
const int maxn=;
int n,m,g[maxn][maxn],vis[maxn][maxn],f[maxn][maxn],sum,cnt,sx,sy,bx,by,flag,ans=0x3f3f3f3f;
struct node{int x,y,num;}; int main(){
scanf("%d%d",&m,&n);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
scanf("%d",&g[i][j]);
if(g[i][j]==) sx=i,sy=j;
else if(g[i][j]==) bx=i,by=j;
else if(g[i][j]==) sum++;
}
queue<node> q; cnt=sum;
q.push((node){sx,sy,}),vis[sx][sy]=;
while(!q.empty()){
node now=q.front(); q.pop();
for(int i=;i<=;i++){
int xx=now.x+mx[i],yy=now.y+my[i];
if(xx>&&xx<=n&&yy>&&yy<=m&&!vis[xx][yy]&&g[xx][yy]!=){
if(g[xx][yy]==&&f[xx][yy]==) f[xx][yy]=now.num+,cnt--;
if(!cnt) goto end;
q.push((node){xx,yy,now.num+}); vis[xx][yy]=;
}
}
}
end: memset(vis,,sizeof(vis));
while(!q.empty()) q.pop(); cnt=sum;
q.push((node){bx,by,}),vis[bx][by]=;
while(!q.empty()){
node now=q.front(); q.pop();
for(int i=;i<=;i++){
int xx=now.x+mx[i],yy=now.y+my[i];
if(xx>&&xx<=n&&yy>&&yy<=m&&!vis[xx][yy]&&g[xx][yy]!=){
if(g[xx][yy]==) ans=min(now.num++f[xx][yy],ans),cnt--;
if(!cnt) goto print;
q.push((node){xx,yy,now.num+}); vis[xx][yy]=;
}
}
}
print: printf("%d",ans);
return ;
}
上一篇:交易所钱包系统搭建流程


下一篇:Java的四种引用