BFS на матрице

Лучшая версия в виде pdf файла Чёрно-белая версия

Постановка задачи

Требуется найти кратчайший путь в матрице (координатной плоскости)

Идея решения

1. Заводим массив d - массив расстояний до данной ячейки от начальных, заполненный -1
2. В начальных ячейках будет хранится 0, так как мы начинаем в них
3. Заводим очередь, в которую загоняем индексы изначальных ячеек
4. Пока очередь не будет пуста (что, в свою очередь говорило бы нам о том, что массив d был подсчитан) забираем элемент сверху и совершаем следующие действия всех смежных ячеек:
   1. Проверяем, не подсчитана ли она уже, иначе продолжаем цикл (оп. continue)
   2. Если не подсчитана, то длина кратчайшего пути до неё будет равна длине кратчайшего пути до предыдущей ячейки + 1
   3. Добавляем данную ячейку в очередь

Реализация

Алгос

To post a comment you need to login first.