Untitled

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int maxn = 55;
const int di[] = {-1, 1, 0, 0};
const int dj[] = {0, 0, -1, 1};
char mat[maxn][maxn];
int n, m;
int dp[maxn][maxn][555];
struct node {
    int ci, cj;
    int time, money;
    node () {}
    node(int _ci, int _cj, int _time, int _money) {
        ci = _ci;
        cj = _cj;
        time = _time;
        money = _money;
    }
    bool operator < (const node &tmp) const {
        if(money == tmp.money) {
            return time > tmp.money;
        }
        return money > tmp.money;
    }
};
short dist[maxn][maxn][maxn][maxn];
void bfs() {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(mat[i][j] == 'M') {
                vector> visited(n, vector(m, false));
                visited[i][j] = true;
                queue q;
                q.push(i);
                q.push(j);
                q.push(0);
                 
                while(!q.empty()) {
                    int ci = q.front(); q.pop();
                    int cj = q.front(); q.pop();
                    int cekor = q.front(); q.pop();
                     
                    if(mat[ci][cj] == 'M') {
                        dist[i][j][ci][cj] = cekor;
                    }
                    for(int k = 0; k < 4; k++) {
                        int ti = ci + di[k];
                        int tj = cj + dj[k];
                        if(ti >= 0 and ti < n and tj >= 0 and tj < m and !visited[ti][tj]) {
                            q.push(ti);
                            q.push(tj);
                            q.push(cekor + 1);
                            visited[ti][tj] = true;
                        }
                    }
                     
                     
                }
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    int stations, t;
    cin >> n >> m >> stations >> t;
     
    int si, sj, ei, ej;
    vector> ms;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> mat[i][j];
            if(mat[i][j] == 'T') {
                si = i;
                sj = j;
            }
            if(mat[i][j] == 'K') {
                ei = i;
                ej = j;
            }
            if(mat[i][j] == 'M') {
                ms.push_back({i, j});
            }
        }
    }
    for(int i = 0; i < maxn; i++) {
        for(int j = 0; j < maxn; j++) {
            for(int k = 0; k <= t; k++) {
                dp[i][j][k] = 2e9;
            }
        }
    }
    priority_queue pq;
    bfs();
    int res_min = 2e9;
    pq.push(node(si, sj, 0, 0));
    while(!pq.empty()) {
        node c = pq.top();
        pq.pop();
         
         
        if(c.ci == ei and c.cj == ej) {
            res_min = min(res_min, c.money);
            continue;
        }
//        cout << c.ci << " " << c.cj << endl;
        if(mat[c.ci][c.cj] == 'M') {
             
            for(int k = 0; k < ms.size(); k++) {
                 
                    int d = dist[c.ci][c.cj][ms[k].first][ms[k].second];
//                    cout << c.ci << " " << c.cj << " " << ms[k].first << " " << ms[k].second << " " << d << " " << c.money << " " << c.time << endl;
                    if(c.time + d <= t and c.money + 5 * d < dp[ms[k].first][ms[k].second][c.time + d]) {
                        pq.push(node(ms[k].first, ms[k].second, c.time + d, c.money + 5 * d));
                        dp[ms[k].first][ms[k].second][c.time + d] = c.money + 5 * d;
                         
                         
                     
                }
            }
        }
        for(int i = 0; i < 4; i++) {
            int ti = c.ci + di[i];
            int tj = c.cj + dj[i];
            if(ti >= 0 and ti < n and tj >= 0 and tj < m and mat[ti][tj] != '#') {
                if(c.time + 5 <= t and c.money < dp[ti][tj][c.time + 5]) {
                    pq.push(node(ti, tj, c.time + 5, c.money));
                    dp[ti][tj][c.time + 5] = c.money;
                     
                     
                }
                if(c.time + 2 <= t and c.money + 1 < dp[ti][tj][c.time + 2]) {
                    pq.push(node(ti, tj, c.time + 2, c.money + 1));
                    dp[ti][tj][c.time + 2] = c.money + 1;
                     
                }
                 
            }
        }
         
    }
        if(res_min == 2e9) {
            res_min = -1;
        }
        cout << res_min << endl;
     
    return 0;
}