問題一覧 > 通常問題

No.2456 Stamp Art

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 60
作問者 : srjywrdnprktsrjywrdnprkt / テスター : 👑 p-adicp-adic
1 ProblemId : 9968 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-08-21 08:57:30

問題文

各マスが白か黒で塗られた縦 $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もしくは右上の雲マークをクリックしてアカウントを作成してください。