Advertisement
Josif_tepe

Untitled

Jun 13th, 2024
450
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.39 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4. int main()
  5. {
  6.   int T;
  7.   cin >> T;
  8.  
  9.   int di[] = {-1, 1, 0, 0};
  10.   int dj[] = {0, 0, -1, 1};
  11.  
  12.   while(T--) {
  13.     int n, m;
  14.     cin >> n >> m;
  15.     char mat[n][m];
  16.     int si, sj, ei, ej;
  17.     for(int i = 0; i < n; i++) {
  18.       for(int j = 0; j < m; j++) {
  19.         cin >> mat[i][j];
  20.  
  21.         if(mat[i][j] == 'S') {
  22.             si = i;
  23.             sj = j;
  24.         }
  25.         if(mat[i][j] == 'E') {
  26.           ei = i;
  27.           ej = j;
  28.         }
  29.       }
  30.     }
  31.  
  32.     queue<int> q;
  33.     q.push(ei);
  34.     q.push(ej);
  35.     q.push(0);
  36.     bool visited[n][m];
  37.     for(int i = 0; i < n; i++) {
  38.       for(int j = 0; j < m; j++) {
  39.         visited[i][j] = false;
  40.       }
  41.     }
  42.     int distanca_od_S = -1;
  43.     visited[ei][ej] = true;
  44.     while(!q.empty()) {
  45.       int ci = q.front();
  46.       q.pop();
  47.       int cj = q.front();
  48.       q.pop();
  49.       int cekor = q.front();
  50.       q.pop();
  51.  
  52.       if(ci == si and cj == sj) {
  53.         distanca_od_S = cekor;
  54.         while(!q.empty()) {
  55.           q.pop();
  56.         }
  57.         break;
  58.       }
  59.       for(int k = 0; k < 4; k++) {
  60.         int ti = ci + di[k];
  61.         int tj = cj + dj[k];
  62.         if(ti >= 0 and ti < n and tj >= 0 and tj < m and !visited[ti][tj] and mat[ti][tj] != 'T') {
  63.           q.push(ti);
  64.           q.push(tj);
  65.           q.push(cekor + 1);
  66.           visited[ti][tj] = true;
  67.         }
  68.       }
  69.  
  70.     }
  71.     for(int i = 0; i < n; i++) {
  72.       for(int j = 0; j < m; j++) {
  73.         visited[i][j] = false;
  74.       }
  75.     }
  76.     visited[ei][ej] = true;
  77.     q.push(ei);
  78.     q.push(ej);
  79.     q.push(0);
  80.     int health_units = 100;
  81.     while(!q.empty()) {
  82.       int ci = q.front();
  83.       q.pop();
  84.       int cj = q.front();
  85.       q.pop();
  86.       int cekor = q.front();
  87.       q.pop();
  88.  
  89.       if(isdigit(mat[ci][cj])) {
  90.         if(cekor <= distanca_od_S) {
  91.             health_units -= (mat[ci][cj] - '0');
  92.         }
  93.       }
  94.       for(int k = 0; k < 4; k++) {
  95.         int ti = ci + di[k];
  96.         int tj = cj + dj[k];
  97.         if(ti >= 0 and ti < n and tj >= 0 and tj < m and !visited[ti][tj] and mat[ti][tj] != 'T') {
  98.           q.push(ti);
  99.           q.push(tj);
  100.           q.push(cekor + 1);
  101.           visited[ti][tj] = true;
  102.         }
  103.       }
  104.     }
  105.     if(health_units < 0) {
  106.       health_units = 0;
  107.     }
  108.     cout << health_units << endl;
  109.  
  110.   }
  111.     return 0;
  112. }
  113.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement