Как осуществить волновой алгоритм поиска кратчайший пути на C++?

Question

[mamadaliev]

Доброго времени суток.
Нужно осуществить волнового алгоритма поиска кратчайший пути в лабиринте. Не понимаю, как осуществить волну в матрице. Помогите.

Answer 1

[f4f]

На википедии есть псевдокод алгоритма, который можно реализовать стандартными конструкциями языка С/С++.

Алгоритм Ли
Инициализируйте двумерный массив типа int. Используйте значение ячейки -1 для стенок лабиринта. В отдельных переменных сохраните индексы начала и конца лабиринта.
Распространение и восстановление волны полностью соответствует описанию алгоритма в вики. Трудность только при растпространении волны в определении последних помеченных ячеек. Для начала можно использовать полный перебор массива, потом усложнить - применить рекурсивные функции или граммотно переделать циклы.

Answer 2

[Василий Васильев]

Недавно писал работу по волновому) Крайне простой способ:
1. присваиваешь точке старта length = 0, остальным - недостижимое число(например, -1). " Стены" по краям - по желанию.
2. В зависимости от выбранных окрестностей(Мура/Мура порядка или Неймана. В Мура в цикле пишется на пару строк кода больше) проверяешь каждую из ближайших точек(через ifelse/switch - по желанию и возможностям. ). Если она равна -1, присваиваешь ей значение length + 1. Если не равна - 1( т.е если мы уже записали в нее расстояние от точки старта length) - пропускаем.
3. length += 1;
Проще всего себе представить(или вывести на экран) прямоугольное поле(оно же - двумерный массив), где все ячейки изначально равны -1, а в точке старта стоит 0. Через while проверять наличие незаписанных клеток(-1) и запускать вышеописанный цикл.
P.S: тоже сначала пытался на сайтах искать, всюду инвалидный рерайт с заумным кодом на восемь страниц. Плюнул, сел сам разобрался(кода на 20 строк), чего и всем советую.

Comments

[xHeAVeNx]

скинь код