Предположим, я начинаю с некоторой вершины (m, n) и хочу достичь вершины (i, j), и на графе есть допустимые пути (значение 1) и недопустимые (значение 0).Я хочу найти уникальное количество путей к (i, j).
Моя текущая идея имеет следующий псевдокод:
Отметить текущий узел из начальногоуказать как посещение, используя переменную-заполнитель, сохранить исходное состояние.
DFS в соседнем узле, где DFS обрабатывает границы и недопустимые пути.Если DFS входит в узел, который посещает (не посещается) в данный момент, остановите DFS, поскольку есть цикл.
Если DFS находит (i, j), увеличивайте значение, чтобы вернуть.
После DFS восстановите исходное состояние ячейки.
Тестирование на нескольких тестовых примерах, это работает, но я не уверен, что этолучшее решение, поскольку сложности потенциально очень велики.Я не очень уверен, если это правильная сложность:
Время: O (M + N) время для каждой DFS, и потенциально выполняет время DFS O (MN), поэтому O(MN * (M + N)) время.
4 вызова на ячейку DFS, поэтому O (4 ^ (MN)) пространство?
Сложность выглядит слишком большой, чтобы быть жизнеспособной.Есть ли лучший алгоритм и правильно ли написана сложность?