KogCoder Code Contest #2 B (AOJ-1160-"How Many Islands?" or "島はいくつある?")

問題

How Many Islands? | Aizu Online Judgeを参照

 

考え方

 

つながっている島(8近傍で隣接している)は1つの島と見なさなければならない.

深さ優先探索を用いて解く.

蟻本の35ページ例題[Lake Counting]が類題となる.

 

プログラム

 

島の有無をboolの2次元配列areaとして扱う.

島があるときをtrue,ないときをfalseとする.

 

count_islandの動作

指定された座標のareaの値をfalseに変える.

8近傍を調べて島が隣接しているならcount_islandにその座標を引数として入れて再帰的に処理を行わせる.

 

count_islandにより1つの島に隣接している島はデータ上なくなる.

隣接していない島はcount_islandでは消せないのでfor文の二重ループで範囲内の全探索を行う.

 

KogCoder-Code-Contest-#2-B