Информатика и технология программирования


Поиск выхода в лабиринте


С точки зрения математики лабиринт представляет собой граф, а алгоритм поиска выхода из него - производит поиск пути, соединяющего заданные вершины. Однако в данном примере мы воспользуемся более простым, естественным представлением лабиринта. Зададим его в виде двумерного массива, в котором значение 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;
}

Однако здесь фиксируем только факт того, что выход найден, но не возвращаем найденный путь. Последнее можно сделать разными способами. Например, использовать те же самые глобальные данные для отметки " хороших" точек




Начало  Назад  Вперед