格子上の経路探索での移動

質問

いまkeiro.jpgのような緑がゴールで赤が壁の場所があります。

緑までの最小距離（上下左右升目）をマッピングしたものが各升の数字になります。

ここで
緑の線と青の線の交点（キョリ７）の位置に駒を置いて最小距離で移動させます。
ここで移動は斜めも可能です。

8方向で最小の場所を求めて進む方法だと青い線を進んでしまいます。
しかし、同じ最小距離の場合
斜めはできるだけ後回し（つまり緑の線）で移動するようにしたいのです。

うまくいかず…どのようにすればいいのでしょうか

距離を求めるアルゴリズムも変更可能です

ただし駒は多いので駒毎に移動方法を算出する事は厳しいです。

回答No.2

noname#147388

先に移動距離計算してやればいいきが。

例：https://ideone.com/nKjez

こんなかんじ

回答No.1

Tacosan

「移動は斜めも可能」ということですが, 例えば青い線をたどると最初でいきなり 7 から 5 と減っています. これは何を意味するのでしょうか? 「斜めに移動できる」なら 1 だけ減っていていいはずですよね.

本題そのものは動的計画法でなんとでもなりそう.

お礼

ありがとうございます
斜めもキョリ1としたら
それだけでできました