← 返回题目列表

Codeforces · 37/E

E. 酋长审判

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

解开《贝尔兰词典》后,科学家们设法阅读了当时编年史家的笔记。例如,他们了解了古代贝兰德部落的首领是如何选出的。

一旦挑选了足够多的冒充者,就会在他们中间进行以下测试:部落的酋长拿一块由水平和垂直条纹划分成相同正方形的石板(石板由N行和M列组成),并将每个正方形涂成黑色或白色。然后,每个觊觎者都会得到一块同样大小但漆成白色的石板。一天之内,伪装者就可以给石板上任何侧面相连的方块涂上一些颜色。如果对于属于该集合的任何两个方格,存在一条属于该集合的路径,且该路径上的任何两个相邻方格共享一条边,则该集合称为链接的。每个冒充者的目标是以与酋长的石板完全相同的方式绘制他的石板。第一个画出这样的石板的人将成为新的酋长。

科学家发现了古代贝尔兰部落酋长所画的石板。如果新酋长必须按照给定的方式粉刷他的石板,请帮助他们确定找到新酋长所需的最少天数。

输入

第一行包含两个整数 N 和 M (1 ≤ N, M ≤ 50) — 板上的行数和列数。接下来的 N 行每行包含 M 个符号——板的最终颜色。 W 代表应涂成白色的正方形,B 代表应涂成黑色的正方形。

输出

在单行输出中,获得板所需着色所需的侧面链接区域的重新绘制次数最少。

示例

输入 #1

3 3
WBW
BWB
WBW

输出 #1

2

输入 #2

2 3
BBB
BWB

输出 #2

1