G - Find a way

 

---

题目分析

        1.双重bfs,遍历两个起点求最短路再计算总和即可

        2.唯一的坑点在于对于一个KFC，两人中可能有一个到不了，所以还要对到不了的点距离做处理

---

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 220;struct pos{int y, x;
}Y, M;char g[N][N];
bool vis[N][N];
int disy[N][N];
int dism[N][N];
int t1, t2;int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};void bfs1()
{memset(vis, 0, sizeof vis);queue<pos> q;q.push(Y);vis[Y.y][Y.x] = 1;while(!q.empty()){pos temp = q.front(); q.pop();for(int i = 0; i < 4; i++){int a = temp.x + dx[i]; int b = temp.y + dy[i];if(a < 1 || b < 1 || a > t2 || b > t1) continue;if(!vis[b][a] && g[b][a] != '#'){vis[b][a] = 1;q.push({b, a});disy[b][a] = disy[temp.y][temp.x] + 1;}}}for(int i = 1; i <= t1; i++){for(int j = 1; j <= t2; j++){if(disy[i][j] == 0) disy[i][j] = 1e7;}}
}void bfs2()
{memset(vis, 0, sizeof vis);queue<pos> q;q.push(M);vis[M.y][M.x] = 1;while(!q.empty()){pos temp = q.front(); q.pop();for(int i = 0; i < 4; i++){int a = temp.x + dx[i]; int b = temp.y + dy[i];if(a < 1 || b < 1 || a > t2 || b > t1) continue;if(!vis[b][a] && g[b][a] != '#'){vis[b][a] = 1;q.push({b, a});dism[b][a] = dism[temp.y][temp.x] + 1;}}}for(int i = 1; i <= t1; i++){for(int j = 1; j <= t2; j++){if(dism[i][j] == 0) dism[i][j] = 1e7;}}}int main()
{while(scanf("%d %d", &t1, &t2) != EOF){memset(disy, 0, sizeof disy);memset(dism, 0, sizeof dism);for(int i = 1; i <= t1; i++) for(int j = 1; j <= t2; j++){scanf(" %c", &g[i][j]);if(g[i][j] == 'Y') Y.x = j, Y.y = i;else if(g[i][j] == 'M') M.x = j, M.y = i;}bfs1();bfs2();int ans = 999;for(int i= 1; i <= t1; i++){for(int j= 1; j <= t2; j++){if(g[i][j] == '@') ans = min(ans, disy[i][j] + dism[i][j]);}}printf("%d\n", ans * 11);}}