双路bfs。
易错:每个bfs都求到KFC的最短路径,然而两次的BFS所到的KFC非同一个KFC。
思路:把Y到全图的最短路径记录,把M到全图的最短路径记录,两个最短路径都用一个数组保存,这样这个数组就是Y和M到该点的最短路径之和。然后遍历@,找出最小1值(别忘记初始化一个很大的值,且最小值不为0)
参考:https://blog.csdn.net/qq_44178862/article/details/99849463
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const ll maxn = 1e6 + 5;
struct node{
int x,y,z;
};
char a[205][205];
int vis[205][205];
int n,m;
int yi,yj,mi,mj,ei,ej;
int dire[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int cnt[205][205];
void bfs(int X,int Y){
node top,now;
queue<node>q;
top={X,Y,0};
q.push(top);
while(!q.empty()){
top=q.front();
q.pop();
now.z=top.z+1;
for(int i=0;i<4;i++){
now.x=top.x+dire[i][0];
now.y=top.y+dire[i][1];
if(!vis[now.x][now.y] && now.x>0 && now.x<=n && now.y>0 && now.y<=m && a[now.x][now.y]!='#'){
vis[now.x][now.y]=1;
cnt[now.x][now.y]+=now.z;
q.push(now);
}
}
}
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
while(cin>>n>>m){
int MAX=0x3f3f3f3f;
memset(a,0,sizeof(a));
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
if(a[i][j]=='Y'){
yi=i;
yj=j;
}
if(a[i][j]=='M'){
mi=i;
mj=j;
}
}
}
memset(vis,0,sizeof(vis));
bfs(yi,yj);
memset(vis,0,sizeof(vis));
bfs(mi,mj);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='@' && cnt[i][j]<=MAX && cnt[i][j]!=0){
MAX=cnt[i][j];
}
}
}
cout<<MAX*11<<endl;
}
return 0;
}