配点

満点

50

問題文

いろんな色をした、同じ大きさの正方形のブロックがH\times Wの長方形に並んでいる。これらのブロックを並び替えて、同じ色のブロックを一直線に並べていくというパズルをやっている。

詳しいルールは次の通りである。

1. 縦か横に同じ色のブロックが3つ以上一直線に並んだら、それらの並んだブロックがくっついて「カタマリ」になる。
   ※この動作は盤面全体で同時に起きる。たとえば同じ色のブロック5個が十字型に並んでいる場合はその5個のブロックから成る1つの「カタマリ」ができる。
2. 同じ色の「カタマリ」同士が一部でも辺を共有している場合、それらは合体して1つの大きな「カタマリ」になる。点のみを共有している場合は合体しない。
3. このプロセスは合体する「カタマリ」がなくなるまで続く。

このゲームにおいて、ブロックを並び替え終わってブロックがくっつき始める直前の盤面が与えられたとき、最終的に何個の「カタマリ」ができるのかを調べたい。

この問題では、ブロックの色は'0'〜'9'の数字で表す。

たとえば次の3つの盤面は、「カタマリ」になるブロックが全て同じ色で上下左右に連結しているため、いずれも1つの「カタマリ」になる。

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\\

入出力例

入力例 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