13

開始、終了、およびいくつかの壁を持つグリッドがあります。ユニットは壁を通過せずに、スタートからゴールまでの最短経路（上下左右のみの移動）をたどります。

最短経路

ユーザーはパスを変更したいだけ壁を追加することができます。

壁を追加する

ただし、いくつの壁を追加しても、どこに追加しても、最短経路の一部にならない正方形がいくつかあることに注意してください。

これらの正方形は、最短経路の一部になることはできません!
これらの正方形は、最短経路の一部になることはできません!

どの正方形が最短経路の一部にならないかを検出する方法を探しています。

上記のケースは簡単に見つけることができます。しかし、もっと複雑なケースがあります。検討：

赤い点のある四角は、ベストパスの一部になることはできません

上の画像では、赤い点で囲まれた四角形はどれも最適なパスの一部になることはありません。そのエリアへの入り口は 1 つしかなく、幅が 2 つしかないからです。3 つのスペースの幅がある場合、または壁のいずれかが取り除かれている場合、それらの正方形のほとんどが最適なパスの一部になる可能性があります。

上記のようなケースを検出する方法を見つけようとしましたが (主に最小カットとフラッド フィルを使用)、成功しませんでした。この問題を解決する方法を知っている人はいますか?

4

2 に答える 2

4

SからFへのパスを検討してください。これらのタイルのみを使用して「ショートカット」を取得できない限り、そのパスは最短パスになる可能性があります（1つおきの正方形を削除した場合）。これは、パス内で隣接していない2つの隣接する正方形がある場合にのみ発生します。したがって、隣接する正方形のすべてのペアを考慮する必要があります。（SをFから切断せずに）SまたはFから切断するものはすべて、最短経路の一部にすることはできません。また、単一の正方形で切断できるタイルは、SからFへのパス（頂点を繰り返さない）の一部にすることはできないため、それらも移動する必要があります。

Nをグリッド内の正方形の数とします。特定の正方形のペア（O（N）があります）の場合、切断されるものは、塗りつぶしを使用してO（N）時間で計算できるため、これはO（N ^ 2）です。試してみたミンカットより安いので、十分安いと思います。

于 2012-09-14T04:30:20.943 に答える
1

最初に、1 つまたは 2 つの隣接するグリッドによってブロックされる可能性のある領域が、最短経路になることは決してないことがわかります。

例のケースを参照してください。ドットをブロックするのは、2 つの黄色のグリッドです。

ここに画像の説明を入力

1 つのグリッドでブロックされていることは理解しやすいです。2人ブロック時：

  1. 隣接していない場合は、余分な壁を追加して、それを唯一のパスにし、一方を通り抜けてもう一方から出ます。そのため、内側のものが必要になる場合があります。
  2. 隣接している場合は、いつでも一方から他方に直接移動できるため、その領域内にグリッドは必要ありません。

したがって、アルゴリズムは次のとおりです。

各空のグリッドを列挙する

  1. その上に壁を置き、フラッドフィルを使用してブロックされた領域を見つけます。それらは役に立ちません。
  2. 隣接する 4 つのグリッド (空​​の場合) の 1 つに壁を設置してみてください。フラッド フィルを使用してブロックされた領域を見つけてください。それらは役に立ちません。
于 2012-09-14T03:42:54.187 に答える