Базовая задача без подводных камней на один из основных алгоритмов теории графов - поиск в ширину. Читаем условие:
Поиск в ширину (волновой алгоритм, BFS) - один из способов обхода графа. Применяется для определения всех вершин, доступных из стартовой (например для нахождения компонент связности), и расстояния до них в невзвешенных графах.
Часто алгоритм называют волновым, потому что схема его работы похожа на расширение кругов на воде:
- сначала выделяется стартовая вершина, до неё расстояние равно 0,
- затем проверяются все соседние с ней вершины, до них расстояние равно 1,
- затем проверяются все соседи вершин с расстоянием 1, которые ещё не были посещены, до них расстояние равно 2,
- и так далее, пока не будут проверены все достижимые вершины вершины.
В алгоритмической реализации нет необходимости явно выделять слои из вершин с одинаковым расстоянием, единственное правило - рассматривать вершины в строгом порядке увеличения расстояния до стартовой. Поэтому можно использовать структуру данных очередь. Или в Python для простоты будем добавлять элементы в список.
Для начала считаем данные: размер таблицы, двумерный массив и стартовую и финишную вершины:
Заведём массив d размера n, в котором будем хранить расстояние до стартовой, и заполним его значениями -1 (можно было бы положить туда что-нибудь большое, но так как при отсутствии пути надо вывести -1, так будет удобнее). Инициализируем нулём расстояние до стартовой вершины, и её же положим в очередь:
Алгоритм будет работать до тех пор, пока не дойдём до конца очереди. На каждом шаге будем обрабатывать очередную вершину из неё:
Для текущей вершины проверяем её соседей (в соответствующей клетке массива m стоит единица) и расстояние от них до стартовой (равно -1, то есть до этой вершины ещё не добирались). Если всё выполняется, то добавляем этого соседа в очередь и запоминаем расстояние от стартовой вершины до него:
Когда закончится цикл, все вершины, до которых можно было добраться из стартовой, будут иметь расстояние до неё. У все остальных оно будет равно -1. Поэтому мы можем очень просто вывести ответ:
Мы рассмотрели самую базовую реализацию поиска в ширину. Для дальнейшего погружения в тонкости этого алгоритма можно посмотреть на разборы задач Задача 703. АСМ-шахматы и Задача 707. Zuma.
Предыдущий выпуск: Задача 664. Котлеты
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.
