题目描述

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

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

• すべてのマスが白、もしくはすべてのマスが黒のとき、複雑さは $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}$ は . となっています。

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

输入格式

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

$H$ $W$ $A_{11}$$A_{12}$$...$$A_{1W}$ $:$ $A_{H1}$$A_{H2}$$...$$A_{HW}$

输出格式

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

题目大意

• 给定一个 $N$ 行 $M$ 列的字符矩阵。
• 我们定义一个字符矩阵的凌乱度为：
  • 若这个字符矩阵中所有字符都相同，则凌乱度为 $0$。
  • 否则，则考虑所有的沿水平或者竖直方向的直线，将字符矩阵分成两个不为空的部分，设两个部分的凌乱度分别为 $a$ 和 $b$，则整个字符矩阵的凌乱度为 $\max(a,b)+1$ 的最小值。
• 请你求出，给出的字符矩阵的凌乱度是多少。
• $1 \leq N, M \leq 185$。

3 3
...
.##
.##

2

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

4

提示

制約

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

Sample Explanation 1

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