「 今週のお題：突進するイノシシ」問題解答 ( CodeIQ )
はじめに
CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。
問題
今回は次のような問題でした。
- ある、障害物が点在する正方形上の格子に対して、猪と餌を配置することを考える。
- 猪は障害物もしくは外壁にぶつかるまで直進する。
- 猪・餌を任意に配置する時の、餌に到達するまでにぶつかる回数( 到達できない配置の場合は 0 回とする ) の最大値を求め、出力する。
- 格子サイズと障害物の配置は入力で与えられる。
参考までに、問題文でサンプルとしてあげられていた5×5の例を図としてあげます。この場合は最大3回ぶつかるため、3を出力します。
解説
べたに、障害物を除く格子毎に猪を配置し、そこから到達できる格子の最多回数を求めます。なお、ぶつかる回数は折れ曲がる回数とみなすことができます。
その際、隣接格子を調べるのではなく、あらかじめ縦・横での連続した格子をグループ化しておいて、一括で扱います。
イメージとしては、次の図のような感じに。便宜上、猪の配置位置を -1 として、縦・横のラインをどんどん埋めていきます。ラインの端が未チェックの格子なら、そこから折れ曲がって、次のラインを処理していきます。最終的に未到達の場所にいけなくなったら ( 未到達の場所が残ることはありうる )、そこで最多回数、ということです。
実装はRubyで行いました。到達済みの格子のチェックについては、整数を1つビット配列とみなして使用しています。上のイメージ図のように、格子毎に回数を埋めるようなことはしていなくて、何ステップで未到達の場所に行けなくなるか、だけを数えています。
終わりに
最近ちょっと囲碁の方に時間を割いていたら遅くなってしまいました。結局全検に近いのですが、もっと効率の良いやりかたあるんでしょうかね。
