Advertisement
Josif_tepe

Untitled

Feb 13th, 2024
574
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.15 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <fstream>
  4. //#include <bits/stdc++.h>
  5. using namespace std;
  6. const int maxn = 1005;
  7. const int INF = 1e9;
  8. const int di[] = {-1, 1, 0, 0};
  9. const int dj[] = {0, 0, -1, 1};
  10. int n, m;
  11. char mat[maxn][maxn];
  12. int dist[maxn][maxn];
  13. void paralel_bfs() {
  14.     queue<int> q;
  15.     vector<vector<bool>> v(n, vector<bool>(m, false));
  16.    
  17.     for(int i = 0; i < n; i++) {
  18.         for(int j = 0; j < m; j++) {
  19.             dist[i][j] = -1;
  20.             if(mat[i][j] == 'G') {
  21.                 q.push(i);
  22.                 q.push(j);
  23.                 q.push(0);
  24.                 v[i][j] = true;
  25.             }
  26.         }
  27.     }
  28.     while(!q.empty()) {
  29.         int ci = q.front(); q.pop();
  30.         int cj = q.front(); q.pop();
  31.         int cekor = q.front(); q.pop();
  32.        
  33.         if(mat[ci][cj] != 'G') {
  34.             dist[ci][cj] = cekor;
  35.         }
  36. //        cout << ci << " " << cj << endl;
  37.         for(int i = 0; i < 4; i++) {
  38.             int ti = ci + di[i];
  39.             int tj = cj + dj[i];
  40.             if(ti >= 0 and ti < n and tj >= 0 and tj < m and dist[ti][tj] == -1 and mat[ti][tj] == '.' and !v[ti][tj]) {
  41.                 q.push(ti);
  42.                 q.push(tj);
  43.                 q.push(cekor + 1);
  44.                 v[ti][tj] = true;
  45.             }
  46.         }
  47.     }
  48.    
  49. }
  50. struct node {
  51.     int ci, cj, d;
  52.     node () {}
  53.     node(int _ci, int _cj, int _d) {
  54.         ci = _ci;
  55.         cj = _cj;
  56.         d = _d;
  57.     }
  58.     bool operator < (const node & tmp) const {
  59.         return d < tmp.d;
  60.     }
  61. };
  62. bool visited[maxn][maxn];
  63. void dijkstra(int si, int sj, int ei, int ej) {
  64.    
  65. }
  66. int main() {
  67.     ios_base::sync_with_stdio(false);
  68. //    ifstream cin("in.txt");
  69.     cin >> n >> m;
  70.     int si, sj, ei, ej;
  71.     for(int i = 0; i < n; i++) {
  72.         for(int j = 0; j < m; j++) {
  73.             cin >> mat[i][j];
  74.             if(mat[i][j] == 'R') {
  75.                 si = i;
  76.                 sj = j;
  77.             }
  78.             if(mat[i][j] == 'Z') {
  79.                 ei = i;
  80.                 ej = j;
  81.             }
  82.         }
  83.     }
  84.     mat[ei][ej] = '.';
  85.     mat[si][sj] = '.';
  86. //    cout << "DA" << endl;
  87.     paralel_bfs();
  88. //    cout << "DA" << endl;
  89.     for(int i = 0; i < n; i++) {
  90.         for(int j = 0; j < m; j++) {
  91.             visited[i][j] = false;
  92.         }
  93.     }
  94.     priority_queue<node> pq;
  95.     pq.push(node(si, sj, dist[si][sj]));
  96.     int min_value = INF;
  97.     while(!pq.empty()) {
  98.         node c = pq.top();
  99.         pq.pop();
  100.         min_value = min(min_value, c.d);
  101.         if(ei == c.ci and ej == c.cj) {
  102.             cout << min_value << endl;
  103.             break;
  104.         }
  105.        
  106. //        cout << c.ci << "  " << c.cj << endl;
  107.         for(int i = 0; i < 4; i++) {
  108.             int ti = c.ci + di[i];
  109.             int tj = c.cj + dj[i];
  110.             if(ti >= 0 and ti < n and tj >= 0 and tj < m and !visited[ti][tj] and mat[ti][tj] == '.') {
  111.                 pq.push(node(ti, tj, dist[ti][tj]));
  112.                 visited[ti][tj] = true;
  113.             }
  114.         }
  115.     }
  116.     return 0;
  117. }
  118. /*
  119.  .R234....
  120.  ..1.3.1..
  121.  ..G121G1.
  122.  ....221..
  123.  G...122..
  124.  ....G12..
  125.  ...**.3..
  126.  ...Z..4..
  127.  
  128.  **/
  129.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement