配点 : $1000$ 点

問題文

この問題のメモリ制限はいつもと異なります。注意してください。

各マスが白か黒で塗られている長方形状のマス目に対して、複雑さ を以下のように定めます。

• すべてのマスが白、もしくはすべてのマスが黒のとき、複雑さは $0$ である。
• そうでないとき、マス目のいずれかの辺に平行な直線でマス目を $2$ つのマス目に分割し、それらのマス目の複雑さを $c_1$, $c_2$ とする。 分割の仕方は複数ありうるが、それらにおける $\max(c_1, c_2)$ の最小値を $m$ として、このマス目の複雑さを $m+1$ とする。

実際に縦 $H$ 行、横 $W$ 列の白黒に塗られたマス目が与えられます。 マス目の状態は $A_{11}$ から $A_{HW}$ の $HW$ 個の文字で表されており、 上から $i$ 行目、左から $j$ 列目にあるマスが黒色のとき $A_{ij}$ は #、 上から $i$ 行目、左から $j$ 列目にあるマスが白色のとき $A_{ij}$ は . となっています。

与えられたマス目の複雑さを求めてください。

制約

• $1 \leq H,W \leq 185$
• $A_{ij}$ は # または .

入力

入力は以下の形式で標準入力から与えられる。

$H$ $W$

$A_{11}$$A_{12}$$...$$A_{1W}$

$:$

$A_{H1}$$A_{H2}$$...$$A_{HW}$

出力

与えられたマス目の複雑さを出力せよ。

3 3
...
.##
.##

2

$1$ 列目と $2$ 列目の境目で $2$ つのマス目に分割してみます。 $1$ 列目だけからなるマス目の複雑さは $0$、$2$,$3$ 列目からなるマス目の複雑さは $1$ なので、 このマス目の複雑さは $2$ 以下だと分かります。

6 7
.####.#
#....#.
#....#.
#....#.
.####.#
#....##

4