bzoj#P3805. Hardwood Cutting

Hardwood Cutting

题目描述

给定一个 n×mn\times m 的矩阵,每个连通块用一个相同的大写或小写字母表示。

每次可以从当前分出的某个块的边界开始,垂直边界切出一条线段,但不能分割连通块。

求最多能把这个矩阵切成多少个块。

输入格式

第一行两个整数 n,mn,m

接下来 nn 行,每行 mm 个字符表示这个矩阵。

输出格式

一行一个整数表示最多能切出的块数。

6 7
CCCDDAA
CCDDDAa
EEEEEEE
EEEZEEE
EEEZEGG
EEEZEGG
5

样例解释

数据规模与约定

对于 100%100\% 的数据,1n,m201\leq n,m\leq 20