第一次解决双向BFS问题，拆分两个出发点分BFS搜索
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 210;
char city[maxn][maxn];
bool visited[maxn][maxn];
int yx, yy, mx, my; //两人的起始点
int kfc[maxn][maxn]; //到达第i,j位置的kfc所需花费的时间（确保该地有kfc）
int action[][2] = { {1,0}, {-1,0}, {0,1}, {0,-1} };
int n, m;
struct Node {
int x, y, steps;
Node(int xx, int yy, int ss) :x(xx), y(yy), steps(ss) { }
};
queue<Node> q[2]; //分别表示两人
void Bfs(int p)
{
memset(visited, 0, sizeof(visited)); //初始化
if (p == 0) {
q[p].push(Node(yx, yy, 0));
visited[yx][yy] = 1;
}
else {
q[p].push(Node(mx, my, 0));
visited[mx][my] = 1;
}
while (!q[p].empty()) {
Node cur = q[p].front();
q[p].pop();
//扩展cur
for (int i = 0; i < 4; i++) {
int sx = cur.x + action[i][0], sy = cur.y + action[i][1];
//为.路(MY也视为路)
if ((sx > 0 && sx <= n && sy > 0 && sy <= m) && !visited[sx][sy] && (city[sx][sy] == '.' || city[sx][sy] == 'M' || city[sx][sy] == 'Y')) {
q[p].push(Node(sx, sy, cur.steps + 1));
visited[sx][sy] = 1;
}
//为@kfc
else if ((sx > 0 && sx <= n && sy > 0 && sy <= m) && !visited[sx][sy] && city[sx][sy] == '@') {
kfc[sx][sy] += cur.steps + 1; //两人步数之和
q[p].push(Node(sx, sy, cur.steps + 1)); //@同样要入队列
visited[sx][sy] = 1;
}
}
}
}
int main()
{
while (scanf("%d%d", &n, &m) != EOF) {
memset(kfc, 0, sizeof(kfc)), memset(city, '#', sizeof(city));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
scanf(" %c", &city[i][j]);
if (city[i][j] == 'Y') yx = i, yy = j;
else if (city[i][j] == 'M') mx = i, my = j;
}
Bfs(0);
Bfs(1);
int ans = 1 << 30; //从各个kfc路径中选出最短的
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (kfc[i][j] != 0 && kfc[i][j] < ans) ans = kfc[i][j];
printf("%d
", ans * 11);
}
return 0;
}