No.2456 Stamp Art
タグ : / 解いたユーザー数 60
作問者 : srjywrdnprkt / テスター : 👑 p-adic
問題文
各マスが白か黒で塗られた縦 $H$ マス横 $W$ マスのグリッド $X$ があります。グリッド $X$ の各マスの色は、#
と .
からなる $H$ 個の長さ $W$ の文字列 $S_1, \cdots, S_H$ で表され、$S_i$ の $j$ 文字目が #
なら、上から $i$ 行目、左から $j$ 列目のマス $(i, j)$ は黒、.
なら白を表します。
全てのマスの色が白である縦 $H$ マス横 $W$ マスのグリッド $Y$ に対して、$H$ 以下かつ $W$ 以下を満たす正整数 $k$ を選んで以下の操作を好きな回数だけ行うことでグリッド $X$ と一致させることが可能であるとき、グリッド $X$ は大きさ $k$ のスタンプで生成可能であるといいます。
(操作)
$1 \leq i \leq H-k+1$ かつ $1 \leq j \leq W-k+1$ を満たす整数のペア $(i, j)$ を選び、$i \leq l \leq i+k-1$ かつ $j \leq m \leq j+k-1$ を満たす全ての整数 $(l, m)$ について、グリッド $Y$ のマス $(l, m)$ の色が白ならば、そのマスを黒に塗り替える。
グリッド $X$ を生成可能なスタンプの大きさの最大値を求めてください。
入力
$H\ W$ $S_1$ $\vdots$ $S_H$
入力は以下の制約を満たす。
- $H, W$ は整数
- $1 \leq H \leq 2000$
- $1 \leq W \leq 2000$
- $S_i$ は
#
か.
のみからなる長さ $W$ の文字列 - $S_i$ の $j$ 文字目が
#
であるような $(i, j)$ が少なくとも $1$ つ存在する。
出力
グリッド $X$ を生成可能なスタンプの大きさの最大値を出力してください。最後に改行してください。
サンプル
サンプル1
入力
3 3 ##. ### .##
出力
2
グリッド $Y$ は最初以下のような状態です。
$k=2$ とした場合を考えます。
まず、$(1,1)$ を選んで操作を行います。すると、グリッド $Y$ は以下のようになります。
次に、$(2,2)$ を選んで操作を行います。すると、グリッド $Y$ は以下のようになり、グリッド $X$ と一致します。
$k\geq 3$ のとき、グリッド $X$ を生成することはできないので $2$ が答えです。
サンプル2
入力
3 3 ### ### ###
出力
3
$k=3$ のとき、$(1,1)$ に対して操作を行えば良いです。
サンプル3
入力
5 6 ###.## ##.### #####. .###.. ######
出力
1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。