uva352 The Seasonal War

UVA の 352 The Seasonal War を解きました。

まずは問題の概要。簡単にいうと、八近傍で隣接するエリアは同じ島として、マップ中の島の数を求めろという感じ。

入力が次のように来ます。入力の終端は EOF 。

6
100100
001010
000000
110000
111000
010100

先頭にサイズ N が来て、その次は N*N のマップ。で、これの島の数を数えると。上の例の場合、

100200
002020
000000
330000
333000
030300

となり答えは 3 です。

簡単な幅優先探索でいけました。ラスタスキャンして、 0 でない点だったらそこを起点に幅優先で 0 塗り。この「塗り」が何回あったかを数えれば答えになる。

AC 数を増やすためにこんな簡単な問題ばかりやってます。