Дано: сетка m × n
Мне нужно перечислить весь путь, который имеет не более одного перекрестка и который заканчивается в верхнем правом углу с использованием обратного хода и рекурсии!? какие-либо предложения .?
Self-Avoiding WalkСамоубеждающая прогулка с использованием обратной рекурсии
Не-рекурсивный способ сохранить стек предыдущих позиций и информации, требующей решения на этой позиции. Каждый раз, когда принимается решение, нажимайте информацию, необходимую для сохранения в верхней части стека.
Тогда, когда ваш поиск в прямом порядке обнаруживает проблему, он выталкивает стек и возвращается к самой последней точке принятия решения и принимает другое решение. В конце концов вы либо преуспеете, либо устраните все возможные пути как невозможные.
Для рекурсивного решения это одно и то же, за исключением того, что вместо того, чтобы вводить информацию в стек, вы передаете новую позицию после принятия решения в рекурсивном вызове. Если рекурсивный вызов возвращает сбой, вы можете попробовать следующее возможное решение в текущей позиции. Если в текущей позиции у вас нет выбора, верните отказ на уровень выше. Только если рекурсивный вызов возвращает успех, этот уровень возвращает успех.
Опять же, в конечном итоге успех возвращается всей цепочке вызовов или устранены все возможные пути.
И поскольку это домашнее задание, вы должны сами решить, какую информацию нужно передавать с одного уровня на другой, и как ваш окончательный путь успеха возвращается в приложение.
Все новые идеи, которые вам нужны, приведены в параграфах выше. Реализация остается за вами.
-Jesse
+1 Хороший ответ на вопрос о домашнем задании. –
Что вы сделали/попробовали? –
Я не знаю, с чего начать! – Rawhi
Очевидной отправной точкой будет алгоритм стиля заливки. Выберите стартовый квадрат (если он не указан) и отметьте его как использованный, затем рекурсивно попробуйте всех его соседей, которые не отмечены как используемые. –