Find a Way

原题链接

题解

要明确一个东西，他们两个人行动不是同步的，所以只要分别对他们两个人跑一边BFS，最后统计最小的时间即可

代码如下

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;
typedef pair<int, int> PII;
const int N = 210;
char g[N][N];
int stM[N][N];
int stY[N][N];
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, -1, 1};

int main(){
    int n, m;
    while(cin >> n >> m){
        int sxy, syy, sxm, sym;
        vector<PII> res;
        for(int i = 0; i < n; ++ i){
            for(int j = 0; j < m; ++ j){
                cin >> g[i][j];
                if(g[i][j] == 'Y') sxy = i, syy = j;
                else if(g[i][j] == 'M') sxm = i, sym = j;
                else if(g[i][j] == '@') res.push_back({i, j});
            }
        }

        memset(stY, -1, sizeof stY);
        memset(stM, -1, sizeof stM);
        queue<PII> q; q.push({sxy, syy});
        stY[sxy][syy] = 0;
        while(q.size()){
            PII t = q.front(); q.pop();
            for(int i = 0; i < 4; ++ i){
                int x = t.first + dx[i], y = t.second + dy[i];
                if(x >= 0 && x < n && y >= 0 && y < m && stY[x][y] == -1 && (g[x][y] == '.' || g[x][y] == '@')){
                    q.push({x, y}), stY[x][y] = stY[t.first][t.second] + 11;
                }
            }
        }

        q.push({sxm, sym}); stM[sxm][sym] = 0;
        while(q.size()){
            PII t = q.front(); q.pop();
            for(int i = 0; i < 4; ++ i){
                int x = t.first + dx[i], y = t.second + dy[i];
                if(x >= 0 && x < n && y >= 0 && y < m && stM[x][y] == -1 && (g[x][y] == '.' || g[x][y] == '@')){
                    q.push({x, y}), stM[x][y] = stM[t.first][t.second] + 11;
                }
            }
        }

        int mmin = 0x3f3f3f3f;
        for(PII it : res){
            if(stY[it.first][it.second] == -1 || stM[it.first][it.second] == -1) continue;
            mmin = min(mmin, stY[it.first][it.second] + stM[it.first][it.second]);
        }
        
        cout << mmin << '
';
    }
    return 0;
}