マス目上の移動のアルゴリズム

質問

このジャンルでお願いします。
下の図で☆がスタートラインで■が移動できるエリアだとします。
15マス移動できるとして、ここでは例えば時計回りに移動するとします。
ただ単に進むだけなら、一歩移動するごとに15（その時の移動可能歩数）から
1ずつ引いていって0になったら動けないようにすれば良いのですが、
移動途中で、進んできた道を戻る場合に移動可能歩数を
回復してやらなければなりません。
どうやってこの道が通ってきた道かを判断すれば良いのでしょうか？

（x=1,y=1）
↓
□□□■□□□
□□□■□□□
□□■☆■■■
□□■□■□■
□□■■■■■
□□■□■□□
□□■■■□□

回答No.2

luckymako · ベストアンサー

スタックを使うのはどうでしょうか？

* 空のスタックを用意します
* 移動する際にスタックに積まれた中の最新の座標と移動先の座標を比較し同じならばスタックから取り除き、ちがければ移動元の座標をスタックに積みます。スタックが空の場合は移動元の座標をスタックに積みます。
* 2の操作を繰り返します。

スタックの大きさが移動した歩数になります。

お礼

ご返答ありがとうございます。
たしかにスタックの大きさが歩数なら分かりやすいですね。

回答No.1

alphion

たとえばスタートの　x=4,y=3　から、
x=4,y=3
x=3,y=3
x=3,y=4
x=3,y=5
x=4,y=5
x=5,y=5
x=5,y=4
x=5,y=3
と移動したときに、次の移動先である
x=4,y=3
を通ってきた道とカウントしないで良いとするなら（どちらを考えているかわかりませんのでとりあえず）、
単純に、移動を行ったら移動前の位置をバッファに保存していき、これから移動する位置とバッファの最後とを比較して、バッファ内にあれば回復とかすればいいだけのような気がします。

お礼

ご返答ありがとうございます。
なるほど、最後だけを比較すればいいわけですか。
なんか難しく考えてました・・・