fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. using ld = long double;
  5.  
  6. const int maxn = 2005;
  7. string s[maxn];
  8. string r[maxn];
  9. int col[maxn][maxn];
  10. int n, m;
  11.  
  12. const int dx[] = {-1, 0, 1, 0};
  13. const int dy[] = {0, -1, 0, 1};
  14. void dfs(int x, int y, int c) {
  15.   col[x][y] = c;
  16.   for (int dir = 0; dir < 4; ++dir) {
  17.     int nx = x + dx[dir];
  18.     int ny = y + dy[dir];
  19.     if (nx < 0 || nx >= n || ny < 0 || ny >= m || s[nx][ny] == '.' || col[nx][ny])
  20.       continue;
  21.     dfs(nx, ny, c);
  22.   }
  23. }
  24.  
  25. const int N = maxn * maxn;
  26. vector<pair<int, int>> g[N];
  27. int dist[N];
  28.  
  29. priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> o;
  30. void dickstra(int u) {
  31.   for (int i = 0; i < N; ++i) {
  32.     dist[i] = 1e9;
  33.   }
  34.   dist[u] = 0;
  35.   o.emplace(dist[u], u);
  36.   while (!o.empty()) {
  37.     int sdist = o.top().first;
  38.     u = o.top().second;
  39.     o.pop();
  40.     if (sdist != dist[u])
  41.       continue;
  42.     for (auto e : g[u]) {
  43.       int v = e.first;
  44.       int w = e.second;
  45.       int ndist = dist[u] + w;
  46.       if (ndist >= dist[v])
  47.         continue;
  48.       dist[v] = ndist;
  49.       o.emplace(dist[v], v);
  50.     }
  51.   }
  52. }
  53.  
  54. signed main() {
  55. #ifdef LOCAL
  56.   assert(freopen("c.in", "r", stdin));
  57. #endif
  58.   cin >> n >> m;
  59.   for (int i = 0; i < n; ++i) {
  60.     cin >> s[i];
  61.     r[i] = string(m, '.');
  62.   }
  63.   int cc = 1;
  64.   for (int i = 0; i < n; ++i) {
  65.     for (int j = 0; j < m; ++j) {
  66.       if (!col[i][j] && s[i][j] == '#')
  67.         dfs(i, j, cc++);
  68.     }
  69.   }
  70.   for (int j = 0; j < m; ++j) {
  71.     int to = 0, dst = -1;
  72.     for (int i = n - 1; i >= 0; --i) {
  73.       ++dst;
  74.       if (s[i][j] == '.')
  75.         continue;
  76.       g[to].emplace_back(col[i][j], dst);
  77.       to = col[i][j];
  78.       dst = -1;
  79.     }
  80.   }
  81.   dickstra(0);
  82.   //for (int i = 0; i < n; ++i) {
  83.     //for (int j = 0; j < m; ++j) {
  84.       //cerr << col[i][j];
  85.     //}
  86.     //cerr << '\n';
  87.   //}
  88.   //for (int i = 0; i < cc; ++i) {
  89.     //cerr << dist[i] << ' ';
  90.   //}
  91.   //cerr << '\n';
  92.   for (int i = 0; i < n; ++i) {
  93.     for (int j = 0; j < m; ++j) {
  94.       if (s[i][j] == '#') {
  95.         int c = col[i][j];
  96.         int sh = dist[c];
  97.         assert(i + sh < n && r[i + sh][j] == '.');
  98.         r[i + sh][j] = '#';
  99.       }
  100.     }
  101.   }
  102.   for (int i = 0; i < n; ++i) {
  103.     cout << r[i] << '\n';
  104.   }
  105. }
  106.  
Success #stdin #stdout 0.05s 141824KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/4URZio
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!