Arti-Jack
@Arti-Jack

Как посчитать кратчайший путь между двумя точками, используя матрицу чисел?

Всех приветствую.

Пишу так называемый Алгоритм Ли (он же унарный/волновой поиск).
Если вкратце, то суть состоит в следующем:
Мы заполняем матрицу числами, перемещаясь волной от точки А до точки В.

Пример:
5a17bc18b8938242310690.png5a17bc256fdfe448748519.png5a17bc2e98991768362793.png

В общем, написать функцию, которая смогла так заполнить матрицу, мне удалось. Я использовал рекурсивные вызовы для левой/правой/верхней/нижней позиции и заполнял сам массив. Но вопоос в следующем: как мне теперь посчитать кратчайший путь?

P.S: Писал я код на Java, но это не имеет весомого значения. Так что можете привести пример на любом языке (но желательно си-подобном или на питоне).
  • Вопрос задан
  • 878 просмотров
Решения вопроса 1
zagayevskiy
@zagayevskiy
Android developer at Yandex
Начиная из конечной точки просто идёшь всегда в сторону наименьшего числа.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы