スタッフBLOG

経路探索22015年10月06日

チューターの田村です。

前回に続き、経路探索の話です。

 

設定を確認すると

5×5のマスの中央にキャラクターがいて、一度に2マスまで進めます。

キャラクターのすぐ上に水たまりがあるときの移動可能な範囲を求めます。

水たまりが無いときは簡単に計算できましたが、今回は少し面倒になります。

 

まず、キャラクターの位置に0と数字を書いておきます。

次に0のマス(キャラクターがいるマス)から上下左右進めるところは1と書きます。

上には水たまりがあり進めないので、下と左右のマスの3箇所に1と書かれます。

次は1のマスから上下左右進めるところは2と書きます。このとき、すでに数字が書かれているマスはそのままにしておきます。

すでに気づいている人もいるかもしれませんが、書いている数字はそこのマスまでの移動距離です。

以上の作業によって数字を書かれたマスには進めると計算できます。

 

これを応用すれば、一度に4マスまで進めるといった場合や、通過するのに2マス分の移動が必要なマスがある場合など、さまざまなパターンのマップで移動可能な範囲を求めることができます。

ぜひ考えて見てください。