vitalk / yandex-shri-minsk-task-2

Второе вступительное задание в Школу разработки интерфейсов Яндекса. Набор 2016 года, Минск

Лабиринт

Карта лабиринта задана матрицей N×M, в которой 0 обозначает пустую клетку, а −1 обозначает стену. Вы стартуете в точке с координатами (x=1; y=0) и на каждом ходу можете перейти на пустую соседнюю точку, расположенную справа, слева, сверху или снизу. Нужно реализовать функцию solution, прокладывающую маршрут до выхода.

Выходов может быть несколько. Точки выхода всегда удовлетворяют условию y=M.

Дополнительная задача: сделать пошаговую визуализацию выполнения алгоритма.

Решение

• Для нахождения выхода используется алгоритм поиска в ширину. Он даёт приемлемые результаты на любом из примеров.

• Для визуализации выполнения алгоритма мне пришлось разделить его отображение на несколько частей:

  • Сам лабиринт,
  • Пошаговая анимация его работы,
  • Найденный путь.