Есть ли решение этой проблемы прохождения?

Question

Скажем, у нас есть матрица M x N, заданная двумя случайно указанными exit и entrance,

найти путь (вверх, вниз, влево, вправо) от entrance до exit, который охватывает каждый узел матрицы только один раз?

Answer 1

Это, очевидно, не всегда решаемо.Скажем, у вас есть эта матрица, где A - вход, а B - выход:

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

Как вы решаете эту проблему?

Answer 2

Одна вещь, которую вы можете попробовать, выглядит примерно так:

Разделите вашу матрицу на две части так, чтобы entrance и exit находились в разных разделах.Затем для каждой действительной пары ячеек, которые образуют «мост» через разбиение, рекурсивно выясняется, существуют ли допустимые пути от entrance до ячейки в ее разбиении и от пары этой ячейки до exit.Если ни одна из пар не работает, то мы не можем найти путь (потому что если такой путь существовал, он должен пересечь этот раздел , в конечном итоге ).

Используя небольшой пример, предположим,у нас было

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

и мы разбили его на середину, чтобы получить

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

, где <-> - единственный действительный «мост».Называя ячейки в этой паре "C" и "D", мы имеем

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

, где мы теперь находим пути от A до C и от D до B. Сращивая эти мини-пути вместе, мы получаем Aот C до D до B.

В примере, приведенном Эмилем, независимо от того, каким образом вы разбиваете эту матрицу, вы не можете получить действительную пару для тестирования, поэтому вы можете сразу сделать вывод, что такого нетпуть.