题目描述

本题的内存限制与通常不同，请注意。

对于一个每个格子都被涂成黑色或白色的矩形网格，我们定义其复杂度如下：

• 如果所有格子都是白色，或者所有格子都是黑色，则复杂度为 $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

输入

3 3
...
.##
.##

输出

2

样例 2

输入

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

输出

4

说明/提示

限制

• $1\leq H,W\leq 185$
• $A_{ij}$ 为 # 或 .

样例解释 1

可以尝试在第 $1$ 列和第 $2$ 列之间分割网格。只包含第 $1$ 列的网格复杂度为 $0$，只包含第 $2$、$3$ 列的网格复杂度为 $1$，因此整个网格的复杂度不超过 $2$。

由 ChatGPT 4.1 翻译