Поиск кратчайшего пути в лабиринте

[DrBreen]

Добрый день.
Будучи студентом,необходимо сдавать задания.
И есть у меня задание по информатике.
Одна там задача беспокоит меня,и задача эта про нахождение кратчайшего пути в лабиринте.
Ладно кратчайший,сначала попытался написать просто поиск пути.
Сделать надобно её именно через рекурсию.
Написал,но она работает только для лабиринтов,в которых нет "петель",то есть круговых путей.
Рекурсивная функция имеет примерно такой вид:
(код под оффтопиком,дабы не засорять экран)

(Оффтоп)

int step(int x,int y,int xp,int yp,int st)
{
   int v,i;
   v=st;
   if((x==n-1)*(y==m-1)) //финальный шаг
   {
      g=v+1;
      s[g].x=x;
      s[g].y=y;
      return 1;
   }

   for(i=0;i<4;i++)
   {
                  
      if((ms[x+dx[i]][y+dy[i]]==0)&&(x+dx[i]>-1)&&(y+dy[i]>-1)&&(x+dx[i]<n)&&(y+dy[i]<m)&&((x+dx[i])!=xp||(y+dy[i])!=yp))
      {
         v++;
         if(step(x+dx[i],y+dy[i],x,y,v)==1)
         {
            s[v].x=x;
            s[v].y=y;
            return 1;
         }
      }
   }
   return 0;
}

dx[i]-это изменение x при движении влево/вверх/вправо/вниз,dy[i]-аналогично.
xp,yp-координаты предыдущей клетки,чтобы программа не скакала,как дурная,по двум клеткам раз за разом.
st-номер клетки в данном пути.
Пусть 1-стена,0-путь. Тогда в лабиринте:
0 0 0 1 1
1 1 0 0 0
1 1 0 1 0
1 1 0 1 0
Программа спокойно ищет выход.
А вот в лабиринте вида:
0 0 0 0 0
1 1 0 1 0
1 1 0 0 0
1 1 1 1 0
она зависает и просто ходит по кругу,отмеченному красным.
Как можно с этим бороться?
Как изменить алгоритм?
Я пытался сделать список "развилочных точек",в которых больше трех путей,чтобы программа на эти точки не ходила более одного раза,однако результата не принесло никакого.

[venco]

Надо помечать те места, где уже был, и не входить в них.
Рекурсия не подходит для поиска кратчайшего пути. Она достаточно быстро найдёт какой-нибудь путь, но для поиска кратчайшего придётся перебирать все возможные пути, что чрезвычайно неэффективно.
Вам нужен поиск вширь (BFS - breadth first search), который я даже не знаю, возможно ли реализовать рекурсивно.

[arseniiv]

А волновой алгоритм тут полезным ли не будет?

Ах рекурсия… Тогда нечего мне сказать. Если только вводить доаолнительные параметры какие-нибудь к функции.

[Circiter]

Любой цикл можно переписать как рекурсию (формально).

P.S.: В данном случае волновая трассировка и BFS -- это одно и то же.

[hurtsy]

DrBreen в сообщении #504896 писал(а):

чтобы программа не скакала,как дурная,по двум клеткам раз за разом.

Несколько обидно за программу, она послушна воле своего творца.

DrBreen в сообщении #504896 писал(а):

Как изменить алгоритм?

Проверить соответствие Вашей реализации( программы) выбранному алгоритму, т.е. избавиться от ошибок, которые как показывает опыт, остаются даже в работающих программах.
Те грабли на которые Вы наступили в теории графов называются циклами. То в чем Вы "обвинили" свою реализацию минимальный цикл.
Алгоритм Вы никак не описали. Про реализацию, Вы не сообщили описание глобальных переменных, поэтому получили от ЗУ общие указания. С уважением,

[Circiter]

Кстати, про проблему циклов при работе волнового алгоритма. Неплох прием с разрушением графа распространяющейся волной -- циклы тоже разрушаются (и память чуть-чуть экономится).

[arseniiv]

(Оффтоп)

Странно, что волновой алгоритм (который я знаю) не шарахается от циклов, которых куча на доске из квадратных клеток.