直大2012.09.06コピーしましたPRアルゴリズムと聞いて、何を思い浮かべますか。この連載では、「アルゴリズム」を、具体的な問題に対して適用していく際の考え方を紹介します。最終回となる今回は、プログラミングコンテスト「TopCoder」で実際に出題された問題を解説します。Fire(燃え広がる迷路)マス目で作られた迷路があります。それぞれのマスは、何も存在しないか、壁があるかのいずれかです。何もないマスの一つに、プレーヤーが操作するキャラクターを置いておきます。ゲーム開始に伴い、何も存在しないマスが、突然燃え始めます。その炎は1ターンごとに隣接する上下左右のマスに広がっていきます。壁のマスには燃え広がりません。あなたはキャラクターを動かして、可能な限り炎から逃げ続けることを目標とします。キャラクターが生き残ることが可能なターン数の最大値を返すプログラムを書きなさい。無限に生き残ることが可能なのであれば、-1を返しなさい。●ゲームのルール・キャラクターはターンごとに隣接する上下左右の空きマスに移動するか、その場所に留まる・炎はターンごとに、隣接する上下左右の空きマスに燃え広がるという進行を繰り返します。キャラクターのいるマスに炎が燃え広がったらゲームオーバーです。迷路はString型の配列mazeとして与えられます。i番目の要素のj文字目の文字が、縦列i番目、横列j番目のマスの状態を表し、文字は'.':空のマス'F':最初に燃え出すマス'#':壁'$':キャラクターの初期位置を表します。入力:{"F..",".$.","..."}戻り値:4上記の入力が与えられた場合、図8のようなゲーム進行となり、4ターン生き延びることが可能となる。よって戻り値は4となる。Fireのゲーム進行の例これは、世界で最も有名な競技プログラミングコンテストの一つであるTopCoderで実際に出題された問題です(別掲記事「競技プログラミングに参加しよう」を参照)。TopCoderの初級者大会で出題されていた3問のうち最も難しい「Hard」のレベルに属する問題ですが、幅優先探索をきちんとマスターできていれば、十分解ける問題です。実際に解き方を考えながら、取り組んでいきましょう。Fireより、TopCoderの許可を得て転載。現場の負担軽減を!医療界でのAWS活用法500万社が導入。情報銀行の成り立ち、事例、現状課題やその行方を網羅。経営戦略である以上、「会計」の知識やスキルが欠かせません。