Существует несколько различных подходов, которые вы можете использовать здесь. Если предположить, что сетка, с которой вы работаете, примерно того же размера, что и показанный выше, и предположить, что вы не обрабатываете, скажем, миллионы сеток одновременно, есть вероятность, что поиск будет как в ширину, так и в глубину. будет работать одинаково хорошо. Преимущество поиска в ширину состоит в том, что он найдет кратчайший путь из любой точки сверху до любой точки снизу; недостатком является то, что обычно требуется больше памяти, чем поиск в глубину. Но опять же, если вы работаете с сетками порядка, скажем, сотен или тысяч ячеек в каждой, есть вероятность, что эти накладные расходы памяти не будут слишком большой проблемой. Я бы сказал, чтобы выбрать тот алгоритм, с которым вам удобнее всего работать, и идти с ним.
Что касается того, как реализовать поиск от «где-нибудь сверху» до «где-нибудь снизу», вы можете добиться этого несколькими различными способами.
Если вы используете поиск в глубину, вы можете запустить один поиск в глубину из каждой ячейки в верхнем ряду и найти путь вниз к нижнему ряду. DFS требует, чтобы вы хранили некоторую информацию о том, какие клетки были и не были посещены. Если вы перерабатываете эту же информацию во всех вызовах DFS, вы гарантируете, что никакие два вызова не будут дублировать работу, и поэтому полученное решение должно быть очень эффективным, работать за время O (mn) в течение m & times; n сетка.
Если вы используете поиск в ширину, модификация довольно проста: вместо того, чтобы ставить в очередь одну начальную точку в очереди в начале поиска, ставьте в очередь каждую ячейку в верхней строке в начало поиска. Затем BFS естественным образом исследует все возможные пути, начиная с любого места в верхнем ряду.
Обе эти идеи можно представить по-разному. Представьте, что ваша сетка представляет собой график , где каждая ячейка является узлом, а ребра соответствуют парам соседних ячеек. Затем вы можете добавить новый узел, который расположен над верхним рядом сетки и связан с каждым из узлов в верхнем ряду. Затем вы добавляете новый узел, который находится чуть ниже нижнего ряда и соединяется с каждым из узлов в нижнем ряду. Теперь, если есть путь от нового верхнего узла к новому нижнему узлу, это означает, что есть путь от некоторого узла в верхней строке к некоторому узлу в нижней строке, поэтому одного поиска в этом графе будет достаточно для Проверьте, существует ли путь. (Интересный факт: две вышеупомянутые модификации DFS и BFS могут рассматриваться как неявно выполняющие поиск в этом новом графе.)
Есть еще один вариант, который вы, возможно, захотите рассмотреть, который довольно прост в реализации и незаметно менее эффективен, чем DFS или BFS, и заключается в использовании структуры данных леса с несвязанным множеством для определения того, что связано. Эта структура данных поддерживает два вида запросов:
- Учитывая две ячейки, отметьте, что есть способ попасть из первой ячейки во вторую. ( "Союз")
- Учитывая две ячейки, определите, существует ли путь между ними, который может быть прямым путем или может быть образован путем объединения нескольких других путей. ( "Найти")
Вы можете реализовать свой запрос на связность, создав лес с несвязанными множествами, объединив все пары соседних ячеек, а затем объединив все узлы в верхнем ряду и объединив все узлы в нижнем ряду. Выполнение запроса «поиск», чтобы увидеть, подключен ли какой-либо из верхних узлов к любому из нижних узлов, решит вашу проблему. Это займет время O (mn & alpha; (mn)) для функции & alpha; (mn), которая растет настолько медленно, что по существу она равна трем или четырем, поэтому она так же эффективна, как BFS или DFS.