SHARE
TWEET

Untitled

a guest Sep 17th, 2017 210 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <climits>
  5. #include <cassert>
  6. #include <vector>
  7. #include <set>
  8.  
  9. using namespace std;
  10.  
  11. typedef unsigned int index;
  12.  
  13. char c[2001][2001];
  14. int comp[2001][2001];
  15. bool u[2001][2001];
  16. int last[2001];
  17. char ans[2001][2001];
  18. int up[2001][2001];
  19. int dt[2001][2001];
  20. int dist[(int) 4e6 + 7];
  21. vector <pair <int, int> > cells[(int) 4e6 + 7];
  22. //vector <pair <int, int> > g[(int) 4e6 + 7];
  23.  
  24. int dx[] = {0, 0, -1, 1};
  25. int dy[] = {-1, 1, 0, 0};
  26.  
  27. int n, m;
  28.  
  29. void dfs(int x, int y, int sz)
  30. {
  31.     cells[sz].push_back({x, y});
  32.     comp[x][y] = sz;
  33.     u[x][y] = true;
  34.     for (int t = 0; t < 4; t++)
  35.     {
  36.         if (x + dx[t] >= 0 && x + dx[t] < n && y + dy[t] >= 0 && y + dy[t] < m && !u[x + dx[t]][y + dy[t]] && c[x + dx[t]][y + dy[t]] == '#')
  37.         {
  38.             dfs(x + dx[t], y + dy[t], sz);
  39.         }
  40.     }
  41. }
  42.  
  43. int main()
  44. {
  45. #ifdef ONPC
  46.     assert(freopen("a.in", "r", stdin));
  47.     assert(freopen("a.out", "w", stdout));
  48. #endif
  49.     scanf("%d%d", &n, &m);
  50.     for (int i = 0; i < n; i++)
  51.     {
  52.         for (int j = 0; j < m; j++)
  53.         {
  54.             scanf(" %c", &c[i][j]);
  55.             ans[i][j] = '.';
  56.         }
  57.     }
  58.     int sz = 0;
  59.     for (int i = 0; i < n; i++)
  60.     {
  61.         for (int j = 0; j < m; j++)
  62.         {
  63.             if (c[i][j] == '#' && !u[i][j])
  64.             {
  65.                 dfs(i, j, sz++);
  66.             }
  67.         }
  68.     }
  69.     for (int j = 0; j < m; j++) last[j] = -1;
  70.     for (int i = 0; i < n; i++)
  71.     {
  72.         for (int j = 0; j < m; j++)
  73.         {
  74.             if (c[i][j] == '#')
  75.             {
  76.                 up[i][j] = -1;
  77.                 if (last[j] != -1 && comp[last[j]][j] != comp[i][j])
  78.                 {
  79.                     up[i][j] = comp[last[j]][j];
  80.                     dt[i][j] = i - last[j] - 1;
  81.                 }
  82.                 last[j] = i;
  83.             }
  84.         }
  85.     }
  86.     for (int i = 0; i < sz; i++) dist[i] = 1e9;
  87.     set <pair <int, int> > s;
  88.     for (int j = 0; j < m; j++)
  89.     {
  90.         if (last[j] != -1 && dist[comp[last[j]][j]] > n - last[j] - 1)
  91.         {
  92.             s.insert({n - last[j] - 1, comp[last[j]][j]});
  93.             dist[comp[last[j]][j]] = n - last[j] - 1;
  94.         }
  95.     }
  96.     while (!s.empty())
  97.     {
  98.         int v = s.begin()->second;
  99.         for (auto go : cells[v])
  100.         {
  101.             int x = go.first, y = go.second;
  102.             ans[x + dist[v]][y] = '#';
  103.             if (up[x][y] != -1)
  104.             {
  105.                 if (dist[up[x][y]] > dist[v] + dt[x][y])
  106.                 {
  107.                     s.erase({dist[up[x][y]], up[x][y]});
  108.                     dist[up[x][y]] = dist[v] + dt[x][y];
  109.                     s.insert({dist[up[x][y]], up[x][y]});
  110.                 }
  111.             }
  112.         }
  113.         s.erase(s.begin());
  114.         /*
  115.         for (auto x : g[v])
  116.         {
  117.             int to = x.first;
  118.             if (dist[to] > dist[v] + x.second)
  119.             {
  120.                 s.erase({dist[to], to});
  121.                 dist[to] = dist[v] + x.second;
  122.                 s.insert({dist[to], to});
  123.             }
  124.         }
  125.         */
  126.     }
  127.     for (int i = 0; i < n; i++)
  128.     {
  129.         for (int j = 0; j < m; j++)
  130.         {
  131.             printf("%c", ans[i][j]);
  132.         }
  133.         puts("");
  134.     }
  135. }
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