AT_agc033_d [AGC033D] Complexity

**本题的内存限制与通常不同，请注意。** 对于一个每个格子都被涂成黑色或白色的矩形网格，我们定义其**复杂度**如下： - 如果所有格子都是白色，或者所有格子都是黑色，则复杂度为 $0$。 - 否则，可以用一条与网格边平行的直线将网格分成两个部分，分别记这两个部分的复杂度为 $c_1$、$c_2$。分割方式可能有多种，取所有分割方式中 $\max(c_1,\ c_2)$ 的最小值为 $m$，则该网格的复杂度为 $m+1$。 现在给定一个高为 $H$ 行、宽为 $W$ 列的黑白网格。网格的状态由 $A_{11}$ 到 $A_{HW}$ 共 $HW$ 个字符表示。第 $i$ 行第 $j$ 列的格子如果是黑色，则 $A_{ij}$ 为 `#`，如果是白色，则 $A_{ij}$ 为 `.`。 请你求出给定网格的复杂度。

输入以如下格式从标准输入读入： > $H$ $W$ > $A_{11}$ $A_{12}$ $...$ $A_{1W}$ > $:$ > $A_{H1}$ $A_{H2}$ $...$ $A_{HW}$

输出给定网格的复杂度。

## 限制 - $1\leq H,W\leq 185$ - $A_{ij}$ 为 `#` 或 `.` ## 样例解释 1 可以尝试在第 $1$ 列和第 $2$ 列之间分割网格。只包含第 $1$ 列的网格复杂度为 $0$，只包含第 $2$、$3$ 列的网格复杂度为 $1$，因此整个网格的复杂度不超过 $2$。 由 ChatGPT 4.1 翻译