結果

問題 No.2456 Stamp Art
ユーザー 👑 hos.lyrichos.lyric
提出日時 2023-09-01 22:10:09
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 169 ms / 5,000 ms
コード長 2,344 bytes
コンパイル時間 1,285 ms
コンパイル使用メモリ 100,408 KB
実行使用メモリ 39,040 KB
最終ジャッジ日時 2024-06-11 17:57:33
合計ジャッジ時間 4,499 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


int M, N;
char A[2010][2010];

int S[2010][2010];
int get(int x0, int x1, int y0, int y1) {
  return S[x0][y0] - S[x0][y1] - S[x1][y0] + S[x1][y1];
}

int f[2010][2010];
bool check(int k) {
  for (int x = 0; x <= M - k; ++x) for (int y = 0; y <= N - k; ++y) {
    f[x + 1][y + 1] = f[x + 1][y] + f[x][y + 1] - f[x][y] + (get(x, x + k, y, y + k) ? 0 : 1);
  }
  for (int x = 0; x < M; ++x) for (int y = 0; y < N; ++y) if (A[x][y] == '#') {
    int x0 = x - k + 1, x1 = x + 1;
    int y0 = y - k + 1, y1 = y + 1;
    chmax(x0, 0); chmin(x1, M - k + 1);
    chmax(y0, 0); chmin(y1, N - k + 1);
    if (f[x0][y0] - f[x0][y1] - f[x1][y0] + f[x1][y1] == 0) {
      return false;
    }
  }
  return true;
}

int main() {
  for (; ~scanf("%d%d", &M, &N); ) {
    for (int x = 0; x < M; ++x) {
      scanf("%s", A[x]);
    }
    
    for (int x = 0; x < M; ++x) for (int y = 0; y < N; ++y) {
      S[x + 1][y + 1] = S[x + 1][y] + S[x][y + 1] - S[x][y] + ((A[x][y] == '.') ? 1 : 0);
    }
    int lo = 0, hi = min(M, N) + 1;
    for (; lo + 1 < hi; ) {
      const int mid = (lo + hi) / 2;
      (check(mid) ? lo : hi) = mid;
    }
    printf("%d\n", lo);
  }
  return 0;
}
0