Mecho

#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("input.txt");
ofstream fout("output.txt");

typedef pair<int, int> pii;
#define r first
#define c second

const int inf = 1e9;
int N, S;
pii start, _end;
queue <pii> q;
vector <vector<char>> m;
vector <vector<int>> bees, dist;
vector <pii> salti = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

pii merge(pii a, pii b){
    return {a.r + b.r, a.c + b.c};
}

//mi creo una matrice dove mi salvo da quando le api saranno in quel punto
void bee(){
    while(!q.empty()){
        auto curr = q.front();
        q.pop();
        for(auto i : salti){
            i = merge(curr, i);
            //se esco dalla mappa, sono su un albero, sono a casa di MECHO o ho già raggiunto la cella
            if(i.r < 0 || i.r >= N || i.c < 0 || i.c >= N || m[i.r][i.c] == 'T' || m[i.r][i.c] == 'D' || bees[i.r][i.c] != inf)
                continue;
            bees[i.r][i.c] = bees[curr.r][curr.c] + 1;
            q.push(i);
        }
    }
}

bool prova(int k){
    queue <pii> que;
    for(auto &i : dist)
        for(auto &j : i)
            j = inf;

    //visto che per sapere quanti minuti sono passati faccio dist/S parto dopo aver fatto K*S passi
    dist[start.r][start.c] = k*S;
    que.push(start);

    while(!que.empty()){
        auto curr = que.front();
        que.pop();

        //le api arrivano prima di MECHO o mentre sono nella cella
        if(dist[curr.r][curr.c] / S >= bees[curr.r][curr.c])
            continue;

        //fine
        if(curr.r == _end.r && curr.c == _end.c)
            return true;

        for(auto i : salti){
            i = merge(i, curr);
            //se esco dalla mappa, sono su un albero, ho già raggiunto la cella
            if(i.r < 0 || i.r >= N || i.c < 0 || i.c >= N || m[i.r][i.c] == 'T' || dist[i.r][i.c] != inf)
                continue;
            dist[i.r][i.c] = dist[curr.r][curr.c] + 1;
            que.push(i);
        }
    }
    return false;
}

int main(){
    fin >> N >> S;
    m.resize(N, vector<char>(N));
    dist.resize(N, vector<int>(N, inf));
    bees.resize(N, vector<int>(N, inf));

    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            fin >> m[i][j];
            switch(m[i][j]){
                case 'M':
                    start = {i, j};
                    break;
                case 'H':
                    q.push({i, j});
                    bees[i][j] = 0;
                    break;
                case 'D':
                    _end = {i, j};
                    break;
                default:
                    break;
            }
        }
    }

    bee();

    int ans = 0;
    int l = 0, u = 800*800+1;
    while(l <= u){
        int mid = (l+u) / 2;
        if(prova(mid)){
            ans = mid;
            l = mid+1;
        }
        else
            u = mid - 1;
    }

    fout << ans;
    return 0;
}