PR

キャラと炎を一緒に考える

 この問題の探索方法は、非常に多く存在しています。どのような状態を持つかなどをきちんと考えなければ、問題を解くことはできません。

図9●人の配置と炎の配置を合わせて探索していく
図9●人の配置と炎の配置を合わせて探索していく

 簡単な方法から見ていきましょう。キャラクターの配置と炎の配置を一緒に探索していく方法です(図9)。ある状態の次のターンで実現可能なキャラクターと炎の配置を、順番に調べていきます。

 この方法でも探索できそうですが、計算時間はどれくらいになるのでしょうか? 縦の長さをh、横の長さをwとして、適当な実装例で考えてみましょう。状態として、キャラクターの場所と炎の状態を表すh*wの配列を持ちます。ここから、空きマスに対して隣接している炎が存在するかを調べていくと、O(4*h*w)程度の計算量になります。

 このとき、状態数はどれくらいあるのでしょうか? キャラクターのいる場所がh*w通りあるので、炎の存在する場所がターンごとに一意に決まることを考慮しても、計算時間が結構かかりそうです。TopCoderのルールでは、一つの問題の実行時間のタイムリミットは2秒なので、オーバーしてしまう可能性がありそうです。

 次の探索方法を考えましょう。炎の配置がターンによって一意に決まることを利用して、炎とキャラクターの配置をそれぞれ分離して探索することにします(図10)。こうすれば、状態ごとに炎の配置を更新する代わりに、1ターン当たり1回の更新で済みます。

図10●炎の配置を人の配置から分離して探索していく
図10●炎の配置を人の配置から分離して探索していく

 この方法では、更新の処理は1回についてO(h*w)の計算量になり、状態数はマスの数を超えないので(h*w)以下となります。1マスに最低1回は炎が燃え広がるので、ターン数はマスの数(h*w)より少なくなるので、計算時間を短くできそうです。