Advertisement
Josif_tepe

Untitled

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