Как реализовать рекурсивную функцию волнового алгоритма на языке c?

Question

[GeekFromUa]

Есть матрица, каждый елемент которой прописан как елемент структуры динамически, с ссылками на соседние елементы как указатели ways (0, 1, 2, 3) - это навравления - вверх, право, низ, лево соответственно.

typedef struct mapItems{
    int id, xPos, yPos, distance, visited;
    struct mapItem *ways[4];
}mapItem;

Написал код который проверяет соседние елементы и записывает туда расстояние

int wave(mapItem *current, int distance){
    printf(" (%d:%d)b=%d-> ", current->xPos, current->yPos, back);
    int i;
    for(i=0; i<4; i++){
        if((current->ways[i]!=0)&&!(current->ways[i]->visited)){
            if(!current->ways[i]->visited){
                current->ways[i]->distance=distance+1;
            }         
        }  
    }

Не могу понять как рекурсировать эту функцию что б оно проверяло поэтапно, тоесть сначала пройшло по кругу все елементы с расстоянием 1, потом волной дальше. У меня получалось, только оно идет в одну сторону. Надо как то передавать переменную внутрь что оно обработало все вокруг и можно идти дальше. Но я не могу догнать как это написать.
Ссылка на алгоритм.

Answer 1

[Rsa97]

Как-то вы перемудрили, рекурсия здесь совершенно не нужна.
Для начала создаём очередь, включаем в неё исходную точку.
Пока очередь не пуста берём из неё точку, всем её доступным незаполненным соседям записываем длину пути и помещаем их в очередь. Можно прервать цикл и раньше, по достижении заданной точки.
Обратным ходом восстанавливаем путь.

Comments

[Олег Цилюрик]

Если речь идёт о поиске минимальных путей, с возможными тупиками и пр. - то только рекурсивный поиск.
Это классическая задача трассировки.

[maaGames]

Олег Цилюрик: Т.е. вас не смущает, что между рекурсией и циклом с сохранением состояний не будет никакой разницы с точки зрения алгоритма?
Поиск в ширину прекрасно реализуется и рекурсией и циклом.
Так что никаких "ТОЛЬКО".

[Олег Цилюрик]

maaGames:
Но поиск в глубину вовсе не так прекрасно реализуется циклом ;-) ... если это просто не формальное разворачивание рекурсии в цикл.

[maaGames]

Олег Цилюрик: Прекрасно он реализуется, я же написал про сохранение состояний. Более того, Rsa97 уже описал реализацию, при помощи очереди. Только там два списка, для текущего и следующего шага "рекурсии".
Тут самое интересное, что реализация с циклом может оказаться эффективнее и с точки зрения использования памяти и по скорости.
А вот поиск в глубину циклом делать уже сильно велосипедостроение.

[maaGames]

Олег Цилюрик: Блин. Невнимательно ваш ответ прочитал и его повторил, по сути.)
Но! Поиск минимального пути эффективнее именно поиском в ширину выполняется, если памяти хватает на его использование.

[Rsa97]

Олег Цилюрик: Рекурсия годится для поиска пути в лабиринте с одиночной шириной коридоров и без петель. Если есть петли или большие комнаты, то можно и не получить кратчайший путь.
Волновой алгоритм гарантирует нахождение кратчайшего пути и не требует рекурсии, очереди вполне достаточно. Можно обойтись и без очереди, просто на каждом шаге просматривая всё поле в поисках клеток с нужной длиной пути.

[Rsa97]

maaGames: Достаточно одной очереди, клетки следующего шага начнут обрабатываться только когда будут извлечены все клетки текущего шага. FIFO, однако.

[Олег Цилюрик]

maaGames:
В конечном итоге, автор задал конкретный вопрос о своей конкретной трудности, и ... "сколько н кричи: халва, халва - во рту слаще не станет" - все эти теоретические глубокомыслия решения его проблемы не приближают ;-)

[maaGames]

Rsa97: волновая трассировка == поиск в ширину. Через рекурсию или цикл - дело вкуса.

[Олег Цилюрик]

Rsa97:

Если есть петли или большие комнаты,

Да ну? ;-)

Всегда приятно получить наставления по теории алгоритмов от специалиста ... по MySQL и JavaScript ;-)
(так по-моему у вас в профиле сформулировано?)

[maaGames]

Rsa97: Действительно. Обычно использовал два вектора, поэтому писать в начало было не выгодно. Про очередь даже не задумывался как-то. Только аллокатор эффективный прикрутить и будет няшно.

[Rsa97]

Олег Цилюрик: Да, тут я поспешил. Можно и кратчайший найти, только надо будет найти все варианты пути, а уже потом выбирать из них.
А в профиле я ничего не указывал, ежели тостер чего подставил, я не смотрел.

[GeekFromUa]

Rsa97: все работает, спасибо большое!

Answer 2

[Олег Цилюрик]

Не могу понять как рекурсировать эту функцию

Вы достаточно сложный вопрос задали + да ещё структур непотребных, избыточно сложных нагородили...
Вы на что рассчитывали?
На то, что вам здесь в 2 слова нарисуют решение задач трассировки?

Написание рекурсивного поиска требует ... определённой привычки. Его в 2 слова не объяснишь.
Вот здесь можете посмотреть: Задачи по программированию на языке C++ - там есть несколько задач (с решениями - cherepah и др.), которые просто повторяют вашу задачу, но в более упрощённой, лёгкой формулировке.

Comments

[GeekFromUa]

Олег Цилюрик Спасибо за критику. Структур наплодил потому что так требует таск, использовать динамические нелинейные данные. Не ожидал что обрисуют, но предыдущий ответ автора Rsa97 вполне устроил. Сейчас попробую реализовать.

[Rsa97]

Тарас: Если такая задача, то можно и очередь представить в виде односвязного списка с добавлением элементов в конец списка и изъятием из начала.

[GeekFromUa]

Rsa97: да, я так и начал делать, и ище две функции для добавления и изъятия. Спасибо