私は仮定し、後で削除します。 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