[AGC033D] Complexity

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

[problemUrl]: https://atcoder.jp/contests/agc033/tasks/agc033_d **この問題のメモリ制限はいつもと異なります。注意してください。** 各マスが白か黒で塗られている長方形状のマス目に対して、 **複雑さ** を以下のように定めます。 - すべてのマスが白、もしくはすべてのマスが黒のとき、複雑さは $ 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} $

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

3 3
...
.##
.##

2

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

4

### 制約 - $ 1\ ≦\ H,W\ ≦\ 185 $ - $ A_{ij} $ は `#` または `.` ### Sample Explanation 1 $ 1 $ 列目と $ 2 $ 列目の境目で $ 2 $ つのマス目に分割してみます。 $ 1 $ 列目だけからなるマス目の複雑さは $ 0 $、$ 2 $,$ 3 $ 列目からなるマス目の複雑さは $ 1 $ なので、 このマス目の複雑さは $ 2 $ 以下だと分かります。