Find a way

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

Pass a year learning in Hangzhou, yifenfei arrival hometown Ningbo at finally. Leave Ningbo one year, yifenfei have many people to meet. Especially a good friend Merceki.
Yifenfei’s home is at the countryside, but Merceki’s home is in the center of city. So yifenfei made arrangements with Merceki to meet at a KFC. There are many KFC in Ningbo, they want to choose one that let the total time to it be most smallest.
Now give you a Ningbo map, Both yifenfei and Merceki can move up, down ,left, right to the adjacent road by cost 11 minutes.

Input

The input contains multiple test cases.
Each test case include, first two integers n, m. (2<=n,m<=200).
Next n lines, each line included m character.
‘Y’ express yifenfei initial position.
‘M’ express Merceki initial position.
‘#’ forbid road;
‘.’ Road.
‘@’ KCF

Output

For each test case output the minimum total time that both yifenfei and Merceki to arrival one of KFC.You may sure there is always have a KFC that can let them meet.

Sample Input

4 4
Y.#@
....
.#..
@..M
4 4
Y.#@
....
.#..
@#.M
5 5
Y..@.
.#...
.#...
@..M.
#...#

Sample Output

66
88
66

题目大意

多组数据，每组数据给一个 n * m 的矩阵，矩阵中 '.' 表示通路，'#' 表示墙，'Y' 表示小朋友1，'M' 表示小朋友2，'@' 表示餐厅。两个小朋友可以上下左右移动，他们希望走进同一家餐厅，每走一步消耗11分钟，要求两人从各自出发点到达该餐厅所花费的时间之和尽可能小。

输出这个最小时间和。

解题思路

这道题是典型的BFS求最短路，要求两个起始点到达同一个终点的路径和最小，只需要分别预处理求出两个起始点到其他它各点的最短距离，然后枚举图中的合法终点即可。一开始本想将枚举所有餐厅进行BFS，找到到达起点1和起点2的最短距离之和，有些逆向思维，但是餐厅数量会很多，这样会很慢，导致TLE。

/*   一切都是命运石之门的选择  El Psy Kongroo  */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
//#include<cmath>
#include<functional>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<double, double> pdd;
typedef pair<string, pii> psi;
typedef __int128 int128;
#define PI acos(-1.0)
#define x first
#define y second
const int inf = 0x3f3f3f3f, mod = 1e9 + 7;


#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;

static const int N = 210;
char g[N][N];
int dist1[N][N], dist2[N][N];
int n, m;
int x1, y1, x2, y2;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
vector<pii> rest;

void bfs(int dist[][N], int sx, int sy){
    queue<pii> q;
    q.push(make_pair(sx, sy));
    dist[sx][sy] = 0;

    while(!q.empty()){
        int x = q.front().first, y = q.front().second;
        q.pop();

        for(int k = 0; k < 4; k ++ ){
            int nx = x + dx[k], ny = y + dy[k];
            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if(g[nx][ny] == '#' || dist[nx][ny] != inf) continue;

            q.push(make_pair(nx, ny));
            dist[nx][ny] = dist[x][y] + 1;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    while(cin >> n >> m){
        rest.clear();
        memset(dist1, 0x3f, sizeof(dist1));
        memset(dist2, 0x3f, sizeof(dist2));
        for(int i = 0; i < n; i ++ )
            for(int j = 0; j < m; j ++ ){
                cin >> g[i][j];
                if(g[i][j] == 'Y') x1 = i, y1 = j;
                if(g[i][j] == 'M') x2 = i, y2 = j;
                if(g[i][j] == '@') rest.push_back(make_pair(i, j));
            }

        bfs(dist1, x1, y1);
        bfs(dist2, x2, y2);

        int res = 1e9;
        for(int i = 0; i < (int)rest.size(); i ++ ){
            int x = rest[i].first, y = rest[i].second;
            res = min(res, dist1[x][y] + dist2[x][y]);  
        }

        cout << res * 11 << endl; 
    }

    return 0;
}