Поиск выхода в лабиринте
С точки зрения математики лабиринт представляет собой граф, а алгоритм поиска выхода из него - производит поиск пути, соединяющего заданные вершины. Однако в данном примере мы воспользуемся более простым, естественным представлением лабиринта. Зададим его в виде двумерного массива, в котором значение 1 будет обозначать " стенку" , а 0-" проход" .
int LB[10][10]={
{1,1,0,1,1,1,1,1,1,1},
{1,1,0,1,1,1,1,1,1,1},
{1,1,0,0,1,0,0,0,1,1},
{1,1,1,0,0,0,1,0,1,1},
{1,0,1,1,1,0,0,0,1,1},
{1,0,0,0,0,0,1,1,1,1},
{1,1,1,1,1,0,1,1,1,1},
{1,1,1,1,1,0,0,0,1,1},
{1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,1,1,1,1,1,1}};
Шаг алгоритма состоит в проверке возможности сделать ход в одном из четырех направлений. Рекурсивный характер алгоритма состоит в том, что в каждой соседней точке реализуется тот же самый алгоритм поиска. Формальными параметрами рекурсивной функции в данном случае являются координаты точки, из которой в данный момент осуществляется поиск. Фактические параметры - координаты соседней точки, в которой реализуется рекурсивный алгоритм.
void step(int x,int y)
{
step(x+1,y);...
step(x,y+1);...
step(x-1,y);...
step(x,y-1);...
}
Результат рекурсивной функции логический - он показывает, можно ли через данную точку достигнуть выхода. Рассмотрим подробнее логику формирования результата на очередном шаге. Если в текущем шаге рекурсии через некоторую соседнюю точку можно достигнуть выхода, то рекурсивный вызов возвратит результат ИСТИНА, который должен быть передан и в предыдущую точку (то есть в предыдущий вызов). Если ни одна соседняя точка не возвращает положительного результата, то результат текущего шага также отрицателен.
int step(int x,int y)
{...
if (step(x+1,y)) return 1;
if (step(x,y+1)) return 1;
if (step(x-1,y)) return 1;
if (step(x,y-1)) return 1;
return 0;
}
Однако здесь фиксируем только факт того, что выход найден, но не возвращаем найденный путь. Последнее можно сделать разными способами. Например, использовать те же самые глобальные данные для отметки " хороших" точек
int step(int x,int y)
{...
if (step(x+1,y)) { LB[x][y]=2; return 1;}
if (step(x,y+1)) { LB[x][y]=2; return 1;}
if (step(x-1,y)) { LB[x][y]=2; return 1;}
if (step(x,y-1)) { LB[x][y]=2; return 1;}
return 0;
}
Следующий шаг - отсечение недопустимых точек, в данном случае это - стенки лабиринта. Здесь же вводится ограничение рекурсии - выход найден, если достигнут край лабиринта :
int step(int x,int y)
{
if (LB[x][y]==1) return 0;
if (x==0 || x==9 || y==0 || y==9) return 1; ...
И, наконец, последнее ограничение. Естественно, что алгоритм не должен возвращаться в ту точку, из которой он только что пришел. Отсюда естественное желание - передавать на вход функции и координаты " предыдущей" точки. Но это не дает гарантии от зацикливания. Так, если в лабиринте есть замкнутые пути, то зацикливание произойдет, даже если помнить предыдущую точку. Выход - в отметке всех пройденных точек лабиринта. Но при этом следует заметить, что каждая точка отмечается только на время рекурсивного вызова, если эти вызовы дают отрицательный результат, то отметка снимается. Предлагаемый ниже вариант с отметками пройденных точек, кроме всего прочего, сохраняет отмеченным путь, который ведет к выходу из лабиринта
//------------------------------------------------------bk54-01.cpp
int step(int x,int y)
{
if (LB[x][y]==1 || LB[x][y]==1) return 0; // стенки и циклы
if (x==0 || x==9 || y==0 || y==9) return 1; // края
LB[x][y]=2; // отметить точку
if (step(x+1,y)) return 1;
if (step(x,y+1)) return 1;
if (step(x-1,y)) return 1;
if (step(x,y-1)) return 1;
LB[x][y]=0; // снять отметку
return 0;
}
