Advertisement
Josif_tepe

Untitled

Mar 16th, 2024
546
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.69 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <fstream>
  5. #include <cstring>
  6. #include <queue>
  7. using namespace std;
  8. typedef long long ll;
  9. const int maxn = 55;
  10. const int di[] = {-1, 1, 0, 0};
  11. const int dj[] = {0, 0, -1, 1};
  12. char mat[maxn][maxn];
  13. int n, m;
  14. int dp[maxn][maxn][555];
  15. struct node {
  16.     int ci, cj;
  17.     int time, money;
  18.     node () {}
  19.     node(int _ci, int _cj, int _time, int _money) {
  20.         ci = _ci;
  21.         cj = _cj;
  22.         time = _time;
  23.         money = _money;
  24.     }
  25.     bool operator < (const node &tmp) const {
  26.         if(money == tmp.money) {
  27.             return time > tmp.money;
  28.         }
  29.         return money > tmp.money;
  30.     }
  31. };
  32. short dist[maxn][maxn][maxn][maxn];
  33. void bfs() {
  34.     for(int i = 0; i < n; i++) {
  35.         for(int j = 0; j < m; j++) {
  36.             if(mat[i][j] == 'M') {
  37.                 vector<vector<bool>> visited(n, vector<bool>(m, false));
  38.                 visited[i][j] = true;
  39.                 queue<int> q;
  40.                 q.push(i);
  41.                 q.push(j);
  42.                 q.push(0);
  43.                  
  44.                 while(!q.empty()) {
  45.                     int ci = q.front(); q.pop();
  46.                     int cj = q.front(); q.pop();
  47.                     int cekor = q.front(); q.pop();
  48.                      
  49.                     if(mat[ci][cj] == 'M') {
  50.                         dist[i][j][ci][cj] = cekor;
  51.                     }
  52.                     for(int k = 0; k < 4; k++) {
  53.                         int ti = ci + di[k];
  54.                         int tj = cj + dj[k];
  55.                         if(ti >= 0 and ti < n and tj >= 0 and tj < m and !visited[ti][tj]) {
  56.                             q.push(ti);
  57.                             q.push(tj);
  58.                             q.push(cekor + 1);
  59.                             visited[ti][tj] = true;
  60.                         }
  61.                     }
  62.                      
  63.                      
  64.                 }
  65.             }
  66.         }
  67.     }
  68. }
  69. int main() {
  70.     ios_base::sync_with_stdio(false);
  71.     int stations, t;
  72.     cin >> n >> m >> stations >> t;
  73.      
  74.     int si, sj, ei, ej;
  75.     vector<pair<int, int>> ms;
  76.     for(int i = 0; i < n; i++) {
  77.         for(int j = 0; j < m; j++) {
  78.             cin >> mat[i][j];
  79.             if(mat[i][j] == 'T') {
  80.                 si = i;
  81.                 sj = j;
  82.             }
  83.             if(mat[i][j] == 'K') {
  84.                 ei = i;
  85.                 ej = j;
  86.             }
  87.             if(mat[i][j] == 'M') {
  88.                 ms.push_back({i, j});
  89.             }
  90.         }
  91.     }
  92.     for(int i = 0; i < maxn; i++) {
  93.         for(int j = 0; j < maxn; j++) {
  94.             for(int k = 0; k <= t; k++) {
  95.                 dp[i][j][k] = 2e9;
  96.             }
  97.         }
  98.     }
  99.     priority_queue<node> pq;
  100.     bfs();
  101.     int res_min = 2e9;
  102.     pq.push(node(si, sj, 0, 0));
  103.     while(!pq.empty()) {
  104.         node c = pq.top();
  105.         pq.pop();
  106.          
  107.          
  108.         if(c.ci == ei and c.cj == ej) {
  109.             res_min = min(res_min, c.money);
  110.             continue;
  111.         }
  112. //        cout << c.ci << " " << c.cj << endl;
  113.         if(mat[c.ci][c.cj] == 'M') {
  114.              
  115.             for(int k = 0; k < ms.size(); k++) {
  116.                  
  117.                     int d = dist[c.ci][c.cj][ms[k].first][ms[k].second];
  118. //                    cout << c.ci << " " << c.cj << " " << ms[k].first << " " << ms[k].second << " " << d << " " << c.money << " " << c.time << endl;
  119.                     if(c.time + d <= t and c.money + 5 * d < dp[ms[k].first][ms[k].second][c.time + d]) {
  120.                         pq.push(node(ms[k].first, ms[k].second, c.time + d, c.money + 5 * d));
  121.                         dp[ms[k].first][ms[k].second][c.time + d] = c.money + 5 * d;
  122.                          
  123.                          
  124.                      
  125.                 }
  126.             }
  127.         }
  128.         for(int i = 0; i < 4; i++) {
  129.             int ti = c.ci + di[i];
  130.             int tj = c.cj + dj[i];
  131.             if(ti >= 0 and ti < n and tj >= 0 and tj < m and mat[ti][tj] != '#') {
  132.                 if(c.time + 5 <= t and c.money < dp[ti][tj][c.time + 5]) {
  133.                     pq.push(node(ti, tj, c.time + 5, c.money));
  134.                     dp[ti][tj][c.time + 5] = c.money;
  135.                      
  136.                      
  137.                 }
  138.                 if(c.time + 2 <= t and c.money + 1 < dp[ti][tj][c.time + 2]) {
  139.                     pq.push(node(ti, tj, c.time + 2, c.money + 1));
  140.                     dp[ti][tj][c.time + 2] = c.money + 1;
  141.                      
  142.                 }
  143.                  
  144.             }
  145.         }
  146.          
  147.     }
  148.         if(res_min == 2e9) {
  149.             res_min = -1;
  150.         }
  151.         cout << res_min << endl;
  152.      
  153.     return 0;
  154. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement