graph-algorithm - このトラバーサル問題の解決策はありますか?

Question

M x N2 つのランダムに指定された と が与えられexitた行列があるとしますentrance。

マトリックス内の各ノードを 1 回だけカバーするからentranceまでのパス (上、下、左、右) を見つけますか?exit

Answer 1

これは明らかに常に解けるわけではありません。この行列があるとします。ここで、A は入口、B は出口です。

+---+---+
| A |   |
+---+---+
|   | B |
+---+---+

これをどのように解決しますか？

Answer 2

あなたが試すことができる1つのことはこのようなものです：

entranceとexitが異なるパーティションにあるように、行列を2つに分割します。entrance次に、分割を介して「ブリッジ」を形成するセルの有効なペアごとに、そのパーティション内のセルへの有効なパスがあるかどうか、およびそのセルのペアからへの有効なパスがあるかどうかを再帰的に見つけますexit。ペアのいずれも機能しない場合、パスを見つけることができません（そのようなパスが存在する場合、最終的にそのパーティションを通過する必要があるため）。

小さな例を使用して、

+---+---+
| A | B |
+---+---+
|   |   |
+---+---+

真ん中で分割して

+---+     +---+
| A |     | B |
+---+     +---+
|   | <-> |   |
+---+     +---+

<->が唯一の有効な「ブリッジ」です。そのペアのセルに「C」と「D」の名前を付けると、次のようになります。

+---+     +---+
| A |     | B |
+---+     +---+
| C | <-> | D |
+---+     +---+

ここで、AからC、およびDからBへのパスが見つかります。これらのミニパスをつなぎ合わせると、AからC、D、Bになります。

Emilの例では、その行列をどのように分割しても、テストする有効なペアを取得できないため、そのようなパスはないとすぐに結論付けることができます。