問題
一辺の長さ１の正方形のタイルが縦に$H$個、横に$W$個長方形状に並べられている。タイルには綺麗なタイルと汚れたタイルの２種類があり、上から$r$番目、左から$c$番目のタイルの種類を$s_{r,c}$とする。$s_{r,c}$が1のとき綺麗なタイルを、0のとき汚れたタイルを表す。
あなたは綺麗なタイルだけを残して、正方形状の枠を作ろうとしている。このときに作れる最大の正方形の一辺の長さを求めよ。なお、以下の条件を全て満たす整数の組$(r_1,c_1,r_2,c_2)$が存在するとき、一辺の長さが$r_2-r_1+1$の正方形の枠が存在するものとする。
- $1 \leq r_1 \leq r_2 \leq H$
- $1 \leq c_1 \leq c_2 \leq W$
- $r_2-r_1=c_2-c_1$
- $c_1 \leq c \leq c_2$を満たす全ての整数の組$(r_1,c)$において$s_{r_1,c}=1$
- $c_1 \leq c \leq c_2$を満たす全ての整数の組$(r_2,c)$において$s_{r_2,c}=1$
- $r_1 \leq r \leq r_2$を満たす全ての整数の組$(r,c_1)$において$s_{r,c_1}=1$
- $r_1 \leq r \leq r_2$を満たす全ての整数の組$(r,c_2)$において$s_{r,c_2}=1$
縦と横のタイルの数、および各タイルの状態が与えられたとき、作ることができる最大の正方形の一辺の長さを求めるプログラムを作成せよ。
入力
入力は以下の形式で与えられる。
$H W$
$s_{1,1}s_{1,2} ... s_{1,W}$
$s_{2,1}s_{2,2} ... s_{2,W}$
:
$s_{H,1}s_{H,2} ... s_{H,W}$
１行目に、縦に並んだタイルの数$H$と横に並んだタイルの数$W$ ($1 \leq H, W \leq 2,000$)が与えられる。続く$H$行に、$H\times W$個のタイルの状態を表す整数$s_{i,j}$ ($0 \leq s_{i,j} \leq 1$)が与えられる。ただし、$s_{i,j}$が1のときは綺麗なタイルを、0のときは汚れたタイルを示す。
出力
作ることができる最大の正方形の一辺の長さを１行に出力する。ただし、正方形の枠が作れない場合は「0」を出力する。
入出力例
入力例１
3 5 11100 10110 11101
出力例１
3
入力例２
4 4 1111 1011 1111 1111
出力例２
4
入力例３
2 2 11 11
出力例３
2
入力例４
2 2 11 10
出力例４
1