アルゴリズムと聞いて、何を思い浮かべますか。「実際にプログラミングを行う上では何に役立つかよくわからない」と感じている方もおられるのではないでしょうか? この連載では、「アルゴリズム」を、具体的な問題に対して適用していく際の考え方を紹介します。最終回となる今回は、プログラミングコンテスト「TopCoder」で実際に出題された問題を解説します。

問題2 ◆ Maze On Fire(燃え広がる迷路)

 マス目で作られた迷路があります。それぞれのマスは、何も存在しないか、壁があるかのいずれかです。何もないマスの一つに、プレーヤーが操作するキャラクターを置いておきます。

 ゲーム開始に伴い、何も存在しないマスが、突然燃え始めます。その炎は1ターンごとに隣接する上下左右のマスに広がっていきます。ただし、壁のマスには燃え広がりません。あなたはキャラクターを動かして、可能な限り炎から逃げ続けることを目標とします。キャラクターが生き残ることが可能なターン数の最大値を返すプログラムを書きなさい。無限に生き残ることが可能なのであれば、-1を返しなさい。

●ゲームのルール
・キャラクターはターンごとに隣接する上下左右の空きマスに移動するか、その場所に留まる
・炎はターンごとに、隣接する上下左右の空きマスに燃え広がる
という進行を繰り返します。キャラクターのいるマスに炎が燃え広がったらゲームオーバーです。

 迷路はString型の配列mazeとして与えられます。i番目の要素のj文字目の文字が、縦列i番目、横列j番目のマスの状態を表し、文字は
'.':空のマス
'F':最初に燃え出すマス
'#':壁
'$':キャラクターの初期位置
を表します。

●プログラムで作成するクラスなど
クラス:MazeOnFire
メソッド:maximumTurns
パラメータ:String[]
戻り値:int
メソッドの表記:int maximumTurns(String[] maze)

●プログラムの制約
・配列mazeには1~50の要素が含まれている
・mazeの要素は、2~50文字で構成されている
・mazeの要素は、すべて同じ文字数とする
・mazeに含まれる文字は、'.','$','#','F'の4種類だけ
・mazeに'$'は必ず一つだけ含まれる

●プログラムの動作例
入力:
{"F..",
".$.",
"..."}
戻り値:4

 上記の入力が与えられた場合、図8のようなゲーム進行となり、4ターン生き延びることが可能となる。よって戻り値は4となる。

図8●Maze On Fireのゲーム進行の例
図8●Maze On Fireのゲーム進行の例

 これは、世界で最も有名な競技プログラミングコンテストの一つであるTopCoderで実際に出題された問題です(別掲記事「競技プログラミングに参加しよう」を参照)。TopCoderの初級者大会で出題されていた3問のうち最も難しい「Hard」のレベルに属する問題ですが、幅優先探索をきちんとマスターできていれば、十分解ける問題です。実際に解き方を考えながら、取り組んでいきましょう。

■参考文献
TopCoder SRM 467 Div2 Hard Maze On Fireより、TopCoderの許可を得て転載。