← 返回题目列表

AtCoder · agc033_d

D. 复杂性

中文机器翻译题面 查看原题

分数: 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