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


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



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;
}




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



Книжный магазин