配点
- 満点
- 50
問題文
各种颜色、大小相同的托盘块H\times W排成长方形。我在玩一种将这些块重新排列,使相同颜色的块排成一条直线的拼图游戏。
详细规则如下。
- 如果纵向或横向相同颜色的块连续排列3个或以上,这些排列在一起的块会结合成“块状物”。
※这个动作会在整个棋盘上同时发生。例如,如果5个相同颜色的方块呈十字形排列,那么由这5个方块组成一个「小块」。 - 如果相同颜色的「小块」之间至少有一部分边相邻,它们会合并成一个更大的「小块」。如果只有点相邻,则不会合并。
- 这个过程会持续,直到没有可以合并的「小块」为止。
在这个游戏中,当给出完成方块排列、方块即将开始粘在一起的棋盘时,我们希望确定最终会形成多少个「小块」。
在这个问题中,方块的颜色用数字 '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