Движок поиска маршрутов

Прежде чем что-то искать, нужно то, в чём искать. Представь сетку так, чтобы каждый алгоритм мог задать одни и те же два вопроса: «кто мои соседи?» и «сколько стоит шаг туда?». Осознанно реши, хранишь ли ты явный список смежности или вычисляешь соседей на лету из (row, col) — для плотной сетки неявная форма экономнее, но написание явной функции `neighbours(node)` заставляет в одном честном месте обработать стены, выбор между четырьмя и восемью направлениями и выход за границы. Взвешенные клетки (скажем, грязь стоит 3, дорога — 1) — это то, что отличает настоящий движок маршрутов от игрушечного лабиринта, поэтому закладывай стоимость в ребро с самого начала, а не прикручивай её потом.

Реализуй поиск в ширину и в глубину и позволь структуре данных стать всем уроком: очередь даёт тебе BFS и кратчайший путь по числу шагов; замени её на стек — и тот же самый код превращается в DFS, который находит *какой-то* путь, но редко кратчайший. По ходу веди множество `visited` и карту `parent`, ведь именно карта parent позволяет восстановить настоящий маршрут после достижения цели — сам поиск лишь сообщает, что цель достижима. Запусти оба на сетке со стеной посередине и понаблюдай, как DFS ныряет вглубь одного коридора, а BFS расширяется кольцами; этот контраст — интуиция, на которой строится весь остальной проект.

BFS считает шаги, но в твоей сетке есть взвешенные клетки, поэтому путь с наименьшим числом шагов и самый дешёвый путь — уже не одно и то же. Dijkstra решает это, всегда раскрывая самый дешёвый на данный момент узел, а значит обычной очереди не хватит — нужна очередь с приоритетом по накопленной стоимости. Реализуй её аккуратно: классическая ошибка — считать узел финальным в момент, когда ты его *увидел*, а не когда *достал* из очереди, что тихо даёт неверные стоимости на графах, где маршрут с большим числом шагов дешевле. Веди карту `dist` и обновляй соседа только тогда, когда нашёл строго более дешёвый путь к нему. Когда всё заработает, объезд по дороге должен побеждать прямую линию через грязь, а напечатанная стоимость пути это докажет.

Dijkstra корректен, но слеп — он раскрывается во все стороны одинаково, тратя работу на клетки, ведущие прочь от цели. A* — это Dijkstra плюс подсказка: в каждом узле он минимизирует `g + h`, где `g` — стоимость пройденного пути, а `h` — оценка оставшейся стоимости до цели. На сетке естественная эвристика для движения по четырём направлениям — манхэттенское расстояние. Незыблемое правило: `h` должна быть *допустимой* — она никогда не должна переоценивать настоящую оставшуюся стоимость, иначе A* может вернуть неверный путь; это тот режим отказа, который нужно намеренно проверять, а не просто прочитать о нём. Когда всё работает, ты увидишь, как поиск раскрывает узкий конус к цели вместо полного диска, и на той же карте A* должен раскрыть строго меньше узлов, чем Dijkstra, вернув ту же оптимальную стоимость.

Подключи все четыре алгоритма к одной команде так, чтобы между запусками менялся только выбранный поиск. Каждый запуск должен печатать одни и те же три факта — путь, стоимость пути и число раскрытых узлов — плюс ASCII-визуализацию исследованной границы, чтобы различия были видны, а не только выражены числами. Именно здесь проект окупается: на одной карте BFS и Dijkstra совпадают, потому что веса плоские, на другой расходятся, а A* повторяет стоимость Dijkstra, затронув меньше клеток. Не вшивай сетку в код — читай её из файла, чтобы создавать каверзные карты (длинный объезд, обманчивая стена), на которых характер каждого алгоритма становится очевидным.