AT_agc033_d [AGC033D] Complexity

[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} $ は `.` となっています。 与えられたマス目の複雑さを求めてください。

N/A

N/A

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