#P3805. Hardwood Cutting
Hardwood Cutting
题目描述
一块长方形木板按单位方格划分。每个方格用一个英文字母或数字标记。同一字符对应一块要保留完整的木料,它的所有格子通过共边相连。大小写字母视为不同字符。
圆锯只能沿网格线直切。一次切割从当前某块木板的边界进入,沿一个固定方向前进,可以在到达另一侧边界之前停下。切线不能经过两个同字符方格的公共边,否则会切开一块要保留的木料。
一次直切可以只切出一道缝,当前木板仍然相连。单独一条还未把木板分开的切缝不会提供新的起锯位置。之后可以从当前木板边界再作其他直切,多道切缝可以接起来,将木板分开。每当一部分已经与其余部分分离,就可以移开它,并从新露出的边界继续切割。
求仅用圆锯最多能把原木板分成多少块。

输入格式
第一行两个整数 (),表示木板的行数和列数。
接下来 行,每行 个英文字母或数字,从上到下给出标记。
输出格式
输出一个整数,表示最多能分成的块数。
样例
6 7
CCCDDAA
CCDDDAa
EEEEEEE
EEEZEEE
EEEZEGG
EEEZEGG
5