障害物がある正方形のグリッドがあります。そのグリッドには、クラスのメンバーが 2 つありPersonます。それらは特定の方向 (上、右、左、または下) を向いています。人にはそれぞれ一定のエネルギーがあります。人を回転させたり移動させたりすると、エネルギーが消費されます (回転は 1 エネルギー ユニットを消費し、移動は 5 エネルギー ユニットを消費します)。
私の目標は、可能な限り最小限のエネルギーを消費して、それらを互いにできるだけ近づけて (マンハッタン距離として表される) 移動させることです。グリッド上に障害物があることに注意してください。
どうすればいいですか？
推測を行い、後で削除します。
グリッドが 1000x1000 よりも小さく、エネルギーが不足しないと仮定すると..:
互いに到達できないと仮定すると、Person1、Person2 について、到達可能なポイントのそれぞれのセット R1、R2 を見つけます。
(たとえば、幅優先検索を使用)
R1 と R2 を x 値で並べ替えます。
次に、R1 と R2 を調べて、最も近い点のペアを見つけます。ヒント: 2 つの配列を並べ替えたので、x 座標に関して点が近い場合がわかります。現在見つかっている最小値よりも x 座標を大きく離す必要はありません。
彼らがお互いに到達できると仮定します: person2 を見つけてパスを記録するまで、person1 から BFS を使用します。
BFS を使用して見つかったパスがターンを必要としない場合、それが解決策です。
さもないと：
グリッドの 4 つのコピーを作成します (それらを右グリッド、左グリッド、上グリッド、下グリッドと呼びます)。
ルールは、左に移動している場合は左のグリッドにのみ入ることができ、右に移動している場合は右のグリッドにのみ入ることができるということです。方向転換するには、1 つのグリッドから別のグリッドに移動する必要があります (エネルギーを消費します)。 ）。
この構造を作成してから、BFS を使用してください。
例：
左側のグリッドは、あなたが左に移動していると想定しているため、左側のグリッドから、すべての点が左側の点に接続され、前方に移動するためのエネルギー量が示されているグラフを作成します。
左グリッドにいるときの他の唯一のオプションは、上グリッドまたは下グリッド (1 エネルギーを使用) への移動であるため、上グリッドと左グリッドなどから対応するグリッドポイントを接続します。
これでグラフが作成されました。幅優先検索を再度使用するだけです。
pythons NetworkX を使用することをお勧めします。約 20 行のコードしかありません。
途中に障害物がある場合は、正方形を接続しないようにしてください。
幸運を。
幅優先探索を使用して、各正方形に到達するための最小エネルギー値を数えます。プレイヤーが出会うか、エネルギーがなくなると終了します。