[autumn_fest_02]3Match
配点
--
満点
50
問題文
いろんな色をした、同じ大きさの正方形のブロックがの長方形に並んでいる。これらのブロックを並び替えて、同じ色のブロックを一直線に並べていくというパズルをやっている。
詳しいルールは次の通りである。
- 縦か横に同じ色のブロックが3つ以上一直線に並んだら、それらの並んだブロックがくっついて「カタマリ」になる。 ※この動作は盤面全体で同時に起きる。たとえば同じ色のブロック5個が十字型に並んでいる場合はその5個のブロックから成る1つの「カタマリ」ができる。
- 同じ色の「カタマリ」同士が一部でも辺を共有している場合、それらは合体して1つの大きな「カタマリ」になる。点のみを共有している場合は合体しない。
- このプロセスは合体する「カタマリ」がなくなるまで続く。
このゲームにおいて、ブロックを並び替え終わってブロックがくっつき始める直前の盤面が与えられたとき、最終的に何個の「カタマリ」ができるのかを調べたい。
この問題では、ブロックの色は'0'〜'9'の数字で表す。
たとえば次の3つの盤面は、「カタマリ」になるブロックが全て同じ色で上下左右に連結しているため、いずれも1つの「カタマリ」になる。
````plain
11122 21223 11111 22111 21111 11111 33133 31233 11111 ```次の2つの盤面は、いずれも2つの「カタマリ」が残る。```plain
111234 111113 234111 222223 ```
与えられた盤面から、最終的に何個の「カタマリ」ができるのかを求めよ。
入力形式
入力は以下の形式で与えられる。
$H W\\ c_1_1c_1_2...c_1_W\\ ...\\ c_H_1c_H_2...c_H_W\\$
出力形式
与えられた盤面からできる「カタマリ」の数を整数で出力せよ。
制約
--
- '0' ≤ c_i_j ≤ '9'
入出力例
入力例 1
3 5
12302
22202
23102
出力例 1
3
次の図のように、3つの「カタマリ」ができる。
図1
入力例 2
3 6
111234
231114
332332
出力例 2
1
'1'の並びが2列できているが、互いに辺を共有しているので1つの「カタマリ」になる。
図2
入力例 3
5 7
1111111
1222321
1223221
1232221
1111111
出力例 3
3
入力例 4
4 4
0011
0011
2334
2994
出力例 4
0
* * *
Writer: tomerun
* * *
Source Name
Autumn Fest
* * *