どう書く？orgの問題に初挑戦。お題は「島の数をカウントする」。１時間少しくらいかかった。最初問題をちゃんと読まずに島の総数を数えていた。
おいらと同じJavaで書いた人が現時点でひとりいて、既にカウントした島の判断方法とか、データの持ち方とかが違うけど、再帰的アルゴリズム使っていて、まあ基本的な流れは同じぽい。
実は１年くらい前、マインスイーパを作ってて、そのときに同じようなコードを書いた。ゲームの中で任意の区画をクリックして、そこに爆弾がなかったら、周辺を調べて同じように爆弾のない区画を全部表示しないといけない。
で、再帰アルゴリズムでひとつひとつ周辺を調べていく方法を用いたんだけど、これが数百×数百みたいな広大なフィールドでやると、スタックが足りなくなってランタイムエラーになったんだよね。
99×99の区画に99個の地雷を置いたフィールド。
スタックオーバーフローして地雷原が途中までしか開いてないの図。
↓
ということで、再帰じゃない方法で書かれてないかなーと見てみたけど、知らん言語が多くてよくわからん。でも大体みんな再帰してるぽいね。なんとなくだけど。