/** * created : 10.11.2024 15:16:44 * author : wzj33300 */ #include using namespace std; #ifdef DEBUG #include #else #define debug(...) 42 #define assert(...) 42 #endif using ll = long long; using u32 = unsigned int; using u64 = unsigned long long; using db = long double; // or double, if TL is tight using str = string; // yay python! // pairs using pi = pair; using pl = pair; using pd = pair; #define fi first #define se second // ^ lol this makes everything look weird but I'll try it template using vc = vector; template using AR = array; using vi = vc; using vb = vc; using vl = vc; using vd = vc; using vs = vc; using vpi = vc; using vpl = vc; using vpd = vc; // vectors // oops size(x), rbegin(x), rend(x) need C++17 #define sz(x) int((x).size()) #define bg(x) begin(x) #define all(x) bg(x), end(x) #define rall(x) x.rbegin(), x.rend() #define sor(x) sort(all(x)) #define rsz resize #define ins insert #define pb push_back #define eb emplace_back #define ft front() #define bk back() #define rep(i, n) for (int i = 0; i < (n); ++i) #define rep1(i, n) for (int i = 1; i < (n); ++i) #define rep1n(i, n) for (int i = 1; i <= (n); ++i) #define repr(i, n) for (int i = (n) - 1; i >= 0; --i) #define rep_subset(t, s) \ for (ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s))) #define lb lower_bound #define ub upper_bound template int lwb(vc &a, const T &b) { return int(lb(all(a), b) - bg(a)); } template int upb(vc &a, const T &b) { return int(ub(all(a), b) - bg(a)); } // const int MOD = 998244353; // 1e9+7; const int Big = 1e9; // not too close to INT_MAX const ll BIG = 1e18; // not too close to LLONG_MAX const db PI = acos((db)-1); const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1}; // for every grid problem!! mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); template using pqg = priority_queue, greater>; int pct(int x) { return __builtin_popcount(x); } int pct(u32 x) { return __builtin_popcount(x); } int pct(ll x) { return __builtin_popcountll(x); } int pct(u64 x) { return __builtin_popcountll(x); } int popcnt_mod_2(int x) { return __builtin_parity(x); } int popcnt_mod_2(u32 x) { return __builtin_parity(x); } int popcnt_mod_2(ll x) { return __builtin_parityll(x); } int popcnt_mod_2(u64 x) { return __builtin_parityll(x); } // (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2) int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); } int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); } int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } // (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2) int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); } int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); } int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } template T floor(T a, T b) { return a / b - (a % b && (a ^ b) < 0); } template T ceil(T x, T y) { return floor(x + y - 1, y); } template T bmod(T x, T y) { return x - y * floor(x, y); } template pair divmod(T x, T y) { T q = floor(x, y); return {q, x - q * y}; } template bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } // set a = min(a,b) template bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } // set a = max(a,b) template T fstTrue(T lo, T hi, U f) { ++hi; assert(lo <= hi); // assuming f is increasing while (lo < hi) { // find first index such that f is true T mid = lo + (hi - lo) / 2; f(mid) ? hi = mid : lo = mid + 1; } return lo; } template T lstTrue(T lo, T hi, U f) { --lo; assert(lo <= hi); // assuming f is decreasing while (lo < hi) { // find first index such that f is true T mid = lo + (hi - lo + 1) / 2; f(mid) ? lo = mid : hi = mid - 1; } return lo; } // signed main() { int main() { ios::sync_with_stdio(false); cin.tie(0); int H, W; cin >> H >> W; H += 2, W += 2; vc> a(H, vc(W, '.')); for (int i = 1; i <= H - 2; i++) for (int j = 1; j <= W - 2; j++) { cin >> a[i][j]; } int ans = 0; vc sum(H + 1, vi(W + 1)); for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) sum[i + 1][j + 1] = sum[i + 1][j] + (a[i][j] == '.'); for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) sum[i + 1][j + 1] += sum[i][j + 1]; auto check = [&](int i, int j, int len) { int xl = i - len, xr = i + len; int yl = j - len, yr = j + len; ckmax(xl, 0), ckmin(xr, H - 1); ckmax(yl, 0), ckmin(yr, W - 1); ++xr, ++yr; return sum[xr][yr] - sum[xr][yl] - sum[xl][yr] + sum[xl][yl] == 0; }; for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) { if (a[i][j] == '#') while (ans < min(H, W) && check(i, j, ans)) ++ans; } cout << ans << '\n'; return 0; }