の角があり、障害物はです。そのグリッドには、クラスの2つのメンバーがありますPerson。彼らは特定の方向（上、右、左または下）に直面しています。それぞれの人には一定のエネルギーがあります。人を回したり動かすことでエネルギーを消費します（旋回は1エネルギー単位を消費し、移動は5エネルギー単位を消費します）。最短経路、最低回転アルゴリズム
私の目標は、できるだけエネルギーを消費しないように、できるだけ近くに（マンハッタンの距離として表現されて）近くに移動させることです。グリッドには障害物があることに注意してください。
どうすればよいですか？
私は幅優先探索を使用し、最小エネルギー値を数えて各四角に到達します。プレイヤーが会うか、それ以上エネルギーが残っていなくても終了します。
私は仮定し、後で削除します。 PERSON1、PERSON2ため を、到達可能なポイントのそれぞれのセットを見つける：彼らはお互いに達することができないと仮定すると、
を..グリッドは1000×1000よりも小さいですし、エネルギーを使い果たすことができないと仮定すると
、R1、R2。
（例えば使用幅優先探索）xの値によって
ソートR1及びR2。
ここでR1とR2を通って、最も近いポイントのペアを見つけてください。 ヒント：2つの配列をソートして、ポイントがいつx座標の点で近いかを知るようにしました。私たちは、現在の最小値よりもx座標上で離れて行く必要はありません。彼らはお互いに達することができると仮定すると、
：使用BFSをPERSON1からBFSを使用して見つかったパスが何ターンを必要としない場合は、PERSON2を見つけて、パス
を記録するまで、そしてそれが解決策である、
そうでない場合：
グリッドのコピーを4つ作成します（右グリッド、左グリッド、上グリッド、下グリッドと呼ぶ）。
ルールは、左に移動している場合は左のグリッドにしか配置できません。右に移動する場合は右のグリッドにしか配置できません。向きを変えるには、1つのグリッドからその他（エネルギーを使用する）。
この構造体を作成し、BFSを使用します。
例：
今左のグリッドはあなたが左に移動していると仮定し、そのすべての点が前方に移動するエネルギーの量を残し、その上の点に接続されている左のグリッドからグラフを作成します。
左グリッドにある唯一の他のオプションは、上グリッドまたは下グリッド（1エネルギーを使用）への移動であるため、上グリッドおよび左グリッドなどから対応するグリッドポイントを接続します。
グラフを作成しました。幅広い最初の検索をもう一度使用してください。
私はPythons NetworkXを使用することをお勧めします。コードは約20行にすぎません。
途中に障害物がある場合は、正方形を接続しないようにしてください。
幸運。
「できるだけ近くに」 - それらの間の距離が障害を説明するか、絶対距離が最小であるべきか？つまり、（移動後に） 'x1-x2 + y1-y2'を最小化するか、結果として得られる（移動後に）' pathfind（）。length'距離を最小化するのはあなたの仕事ですか？私は十分に明確であることを望む。 – bezmax
マンハッタン距離 'abs（x1-x2）+ abs（y1-y2）'は、障害物を考慮せずにできるだけ小さくする必要があります。 – Fatso