← 返回题目列表

AtCoder · autumn_fest_02

B. 3场比赛

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

配点

満点
50

問題文

各种颜色、大小相同的托盘块H\times W排成长方形。我在玩一种将这些块重新排列,使相同颜色的块排成一条直线的拼图游戏。

详细规则如下。

  1. 如果纵向或横向相同颜色的块连续排列3个或以上,这些排列在一起的块会结合成“块状物”。
    ※这个动作会在整个棋盘上同时发生。例如,如果5个相同颜色的方块呈十字形排列,那么由这5个方块组成一个「小块」。
  2. 如果相同颜色的「小块」之间至少有一部分边相邻,它们会合并成一个更大的「小块」。如果只有点相邻,则不会合并。
  3. 这个过程会持续,直到没有可以合并的「小块」为止。

在这个游戏中,当给出完成方块排列、方块即将开始粘在一起的棋盘时,我们希望确定最终会形成多少个「小块」。

在这个问题中,方块的颜色用数字 '0' 到 '9' 表示。

例如,下列三个棋盘,由于所有会形成「小块」的方块都是相同颜色并在上下左右方向相连,因此它们都将形成一个「小块」。

11122   21223   11111
22111   21111   11111
33133   31233   11111
以下两个棋盘上,都剩有两个“塊”。
111234  111113
234111  222223

请从给定的棋盘中,求出最终可以形成多少个“塊”。

入力形式

输入以以下格式给出。

H\ W\\
c_1_1c_1_2...c_1_W\\
...\\
c_H_1c_H_2...c_H_W\\

出力形式

请输出从给定棋盘中可以形成的“塊”的数量(整数)。

制約

  • 3 ≤ H,\ W ≤ 100
  • '0' ≤ c_i_j ≤ '9'

入出力例

入力例 1

3 5
12302
22202
23102

出力例 1

3

如下图所示,可以形成三个“塊”。

図1

入力例 2

3 6
111234
231114
332332

出力例 2

1

虽然有两列“1”排列,但由于它们共享边,因此只形成一个“塊”。

図2

入力例 3

5 7
1111111
1222321
1223221
1232221
1111111

出力例 3

3

入力例 4

4 4
0011
0011
2334
2994

出力例 4

0

作者: tomerun