26.08.2006, 19:59
общий
это ответ
Здравствуйте, KInika!
Если у вас лабиринт на прямоугольной матрице, то наиболее простым, хотя, конечно, не самым быстрым, будет алгоритм типа заливки. Для него, опять же, проще всего, создать вспомогательный двумерный массив переменных типа Word или даже Integer.
В лабиринте, где довольно мало ходов и много стен, эффективнее было бы создавать передвигающихся "агентов", но это я сходу не скажу, как сделать.
В примере написана рекурсивная процедура. Она тоже - не самая эффективная, т.к. находит кратчайшее расстояние сразу до всех точек от указанной во входной процедуре (числа, которые будут записаны в ячейках HelpArray и будут расстояниями до точки с координатами, которые вы передадите процедуре Flood при ее вызове)
А вот если вам понадобиться востановить еще и путь(маршрут), то это уже сложнее - понадобиться либо сохранять дополнительную информацию, либо писать еще одну рекурсивную процедуру и уже по готовому HelpArray вычислять маршрут.
Приложение:
var HelpArray: array[1..N, 1..N] of integer;// заполняем массивfor i := 1 to N do for j := 1 to N do if {если там дложна быть стенка} HelpArray[i,j] := -1; else HelpArray[i,j] := MAX_INT;// рекусривная процедура вызова.procedure Flood(x,y,len: integer);begin HelpArray[x,y] := len; inc(len); if (x > 1) and (HelpArray[x-1,y] > len) then Flood(x-1,y,len); if (x < N) and (HelpArray[x+1,y] > len) then Flood(x+1,y,len); if (y > 1) and (HelpArray[x,y-1] > len) then Flood(x,y-1,len); if (y < N) and (HelpArray[x,y+1] > len) then Flood(x,y+1,len);end;// Теперь осталось вызвать процедуру в теле программы:Flood(x1, y1, 0);// и прочесть значение расстояния до точки (x2; y2)distance := HelpArray[x2, y2];