fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define pll pair<ll, ll>
  5. #define mp make_pair
  6. #define fi first
  7. #define se second
  8. ll N, M;
  9. const ll NI[] = { -1, -1, -1,  0, 0,  1, 1, 1 };
  10. const ll NJ[] = { -1,  0,  1, -1, 1, -1, 0, 1 };
  11. int main() {
  12.     cin >> N >> M;
  13.     vector<vector<char>> a(N, vector<char>(M, 0));
  14.     vector<vector<ll>> dist(N, vector<ll>(M, -1));
  15.     queue<pll> bfs;
  16.     for (int i = 0; i < N; i++) {
  17.         for (int j = 0; j < M; j++) {
  18.             cin >> a[i][j];
  19.         }
  20.     }
  21.     for (int i = 0; i < N; i++) {
  22.         for (int j = 0; j < M; j++) {
  23.             if (a[i][j] == '.') continue;
  24.             for (int k = 0; k < 8; k++) {
  25.                 int ni = i + NI[k];
  26.                 int nj = j + NJ[k];
  27.                 if (ni < 0 || ni >= N || nj < 0 || nj >= M || a[ni][nj] == '.') {
  28.                     bfs.push(mp(i, j));
  29.                     dist[i][j] = 0;
  30.                     break;
  31.                 }
  32.             }
  33.         }
  34.     }
  35.     ll maxd = 0;
  36.     while (!bfs.empty()) {
  37.         pll cur = bfs.front();
  38.         bfs.pop();
  39.         for (int k = 0; k < 8; k++) {
  40.             int ni = cur.fi + NI[k];
  41.             int nj = cur.se + NJ[k];
  42.             if (ni < 0 || ni >= N || nj < 0 || nj >= M || a[ni][nj] == '.' || dist[ni][nj] != -1) continue;
  43.             dist[ni][nj] = dist[cur.fi][cur.se] + 1;
  44.             maxd = max(maxd, dist[ni][nj]);
  45.             bfs.push(mp(ni, nj));
  46.         }
  47.     }
  48.  
  49.     ll l = 0;
  50.     ll r = maxd;
  51.     ll T, mid;
  52.     while (l <= r) {
  53.         mid = (l + r)/2;
  54.         vector<vector<ll>> dist2(N, vector<ll>(M, -1));
  55.         for (int i = 0; i < N; i++) {
  56.             for (int j = 0; j < M; j++) {
  57.                 if (dist[i][j] >= mid) {
  58.                     bfs.push(mp(i, j));
  59.                     dist2[i][j] = 0;
  60.                 }
  61.             }
  62.         }
  63.         while (!bfs.empty()) {
  64.             pll cur = bfs.front();
  65.             bfs.pop();
  66.             for (int k = 0; k < 8; k++) {
  67.                 int ni = cur.fi + NI[k];
  68.                 int nj = cur.se + NJ[k];
  69.                 if (ni < 0 || ni >= N || nj < 0 || nj >= M || a[ni][nj] == '.' || dist2[ni][nj] != -1) continue;
  70.                 dist2[ni][nj] = dist2[cur.fi][cur.se] + 1;
  71.                 // maxd = max(maxd, dist2[ni][nj]);
  72.                 if (dist2[ni][nj] < mid) bfs.push(mp(ni, nj));
  73.             }
  74.         }
  75.  
  76.         bool valid = true;
  77.         for (int i = 0; i < N; i++) {
  78.             for (int j = 0; j < M; j++) {
  79.                 if ((a[i][j] == 'X') != (dist2[i][j] != -1)) valid = false;
  80.             }
  81.         }
  82.  
  83.         if (valid) {
  84.             T = mid;
  85.             l = mid+1;
  86.         } else r = mid-1;
  87.     }
  88.  
  89.     cout << T << endl;
  90.     for (int i = 0; i < N; i++) {
  91.         for (int j = 0; j < M; j++) {
  92.             if (j != 0) cout << " ";
  93.             cout << (dist[i][j] >= T ? 'X' : '.');
  94.         }
  95.         cout << endl;
  96.     }
  97. }
  98.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/omh0H0
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

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!