SHARE
TWEET

Untitled

a guest Apr 20th, 2019 84 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 2000;
  6. const int INF = INT_MAX;
  7. vector<int> g[N];
  8. vector<int> vamp;
  9. int mark[N * N];
  10. int a[N][N];
  11. int n, m;
  12. unsigned int counter = 0;
  13.  
  14. bool bounds(int i, int j) {
  15.     return i < n && j < n && i >= 0 && j >= 0;
  16. }
  17.  
  18. void bfs(int v) {
  19.     vector<char> used(counter, false);
  20.     mark[v] = 0;
  21.     used[v] = true;
  22.     queue<int> q;
  23.     q.push(v);
  24.     while(!q.empty()) {
  25.         int u = q.front();
  26.         q.pop();
  27.         for(auto to : g[u]) {
  28.             if(!used[to]) {
  29.                 used[to] = true;
  30.                 mark[to] = min(mark[to], mark[u] + 1);
  31.                 q.push(to);
  32.             }
  33.         }
  34.     }
  35.  
  36. }
  37.  
  38. int main() {
  39.     freopen("vampires.in", "r", stdin);
  40.     freopen("vampires.out", "w", stdout);
  41.     ios::sync_with_stdio(false);
  42.  
  43.     cin >> n >> m;
  44.     for(int i = 0; i < n; ++i) {
  45.         cin.get();
  46.         for(int j = 0; j < m; ++j) {
  47.             mark[m * i + j] = INF;
  48.             char symb;
  49.             cin.get(symb);
  50.             if(symb == 'V' || symb == '.') {
  51.                 a[i][j] = counter++;
  52.                 if(symb == 'V') {
  53.                     vamp.push_back(a[i][j]);
  54.                 }
  55.             } else {
  56.                 a[i][j] = -1;
  57.             }
  58.         }
  59.     }
  60.     for(int i = 0; i < n; ++i) {
  61.         for(int j = 0; j < m; ++j) {
  62.             if(a[i][j] == -1) {
  63.                 continue;
  64.             }
  65.             if(bounds(i - 1, j) && a[i - 1][j] != -1)
  66.                 g[a[i - 1][j]].push_back(a[i][j]);
  67.             if(bounds(i + 1, j) && a[i + 1][j] != -1)
  68.                 g[a[i + 1][j]].push_back(a[i][j]);
  69.             if(bounds(i, j - 1) && a[i][j - 1] != -1)
  70.                 g[a[i][j - 1]].push_back(a[i][j]);
  71.             if(bounds(i, j + 1) && a[i][j + 1] != -1)
  72.                 g[a[i][j + 1]].push_back(a[i][j]);
  73.         }
  74.     }
  75.  
  76.     for(auto v : vamp) {
  77.         bfs(v);
  78.     }
  79.  
  80.     int max = -1;
  81.     for(int i = 0; i < counter; ++i) {
  82.         if(mark[i] > max) {
  83.             max = mark[i];
  84.         }
  85.     }
  86.  
  87.     cout << max;
  88. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top