分数: 1000 点
问题陈述
注意异常的内存限制。
对于每个正方形都漆成白色或黑色的矩形网格,我们定义其 复杂性 如下:
- 如果所有方块都是黑色或所有方块都是白色,则复杂度为 0.
- 否则,用一条平行于网格一侧的线将网格划分为两个子网格,并让 c_1 和 c_2 是子网格的复杂性。可以有多种方法来执行除法,让 m 是最小值 \max(c_1, c_2) 在那些部门。网格的复杂度为 m+1.
给你一个网格 H 水平行和 W 垂直列,其中每个方块被漆成白色或黑色。
HW 字符来自 A_{11} to A_{HW} 代表方块的颜色。
A_{ij} is # 如果正方形位于 i从顶部开始的第行和 j从左边算起的第列是黑色的,并且 A_{ij} is . 如果该方块是白色的。
求给定网格的复杂度。
约束
- 1 \leq H,W \leq 185
- A_{ij} is
#or..
输入
输入由标准输入按以下格式给出:
H W
A_{11}A_{12}...A_{1W}
:
A_{H1}A_{H2}...A_{HW}
输出
打印给定网格的复杂性。
示例输入 1
3 3 ... .## .##
示例输出 1
2
让我们用第一列和第二列之间的边界线来划分网格。 由第一列组成的子网格的复杂度为 0,由第二列和第三列组成的子网格的复杂度为 1,所以整个网格的复杂度最多为 2.
示例输入 2
6 7 .####.# #....#. #....#. #....#. .####.# #....##
示例输出 2
4