题目:
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 ;
}