Волновой алгоритм

[Adelia]

Всем,добрый вечер)
Прошу,помогите разобраться с волновым алгоритмом.Сам принцип мне вроде ясен.Но вот нашла пример задачи и не могу в нем разобраться)

Задача: «Однажды Джеку Воробью принесли весть, что на одном из Карибских островов спрятан клад. Клад этот спрятан в пещере и путь к нему подобен лабиринту. Пирату удалось выкрасть карту лабиринта. И вот, отважный пират отправился на поиски клада. Продвигаясь по лабиринту, он заплутал. Волшебный компас показал координаты его расположения и координаты места, где расположен клад. Помоги Джеку отыскать клад».
Решение: требуется написать программу, которая по заданному описанию лабиринта и указанию начальных и конечных координат путника напечатает возможный кратчайший путь к кладу.
Формат входных данных:
Первая строка содержит размерность лабиринта, а именно М – число строк в описании лабиринта, и N – число столбцов (M, N <15). Далее вводится числовая матрица MxN, содержащая описание лабиринта, где стены отмечены 1, а проходы - 0. Затем вводятся координаты Джека Воробья (номер строки и столбца (XS, YS), где он находится в текущий момент) и координаты, где расположен клад (XF, YF).
Формат выходных данных:
Найти ближайший путь к кладу и напечатать описание лабиринта вместе с намеченным путем. Начало пути пометить цифрой 2. В местах, где пролегает путь, выставить цифру 3, а в месте клада – 4. Вывести длину пути.

Вот решение этой задачипожалуйста подскажите для чего нужны массивы Mas и Masm, массив Mas как я поняла хранит в себе карту лабиринта)

Program Voln;
Var 
   XS, YS, XF, YF : Byte; 
   X, Y, K, M, N : Byte;
   Mas, Masm : array [1..15, 1..15] of Byte; 
   Step: byte;
   Procedure Next(Var X, Y : Byte); {поиск клетки, куда возможен шаг}
   Begin
      If (X <M) and (MasM[X, Y] - MasM[X + 1, Y] = 1) then Begin X := X + 1; Exit; End;
      If (X >1) and (MasM[X, Y] - MasM[X - 1, Y] = 1) then Begin X := X - 1; Exit; End;
      If (Y <N) and (MasM[X, Y] - MasM[X, Y + 1] = 1) then Begin Y := Y + 1; Exit; End;
      If (Y >1) and (MasM[X, Y] - MasM[X, Y - 1] = 1) then Begin Y := Y - 1;  Exit; End;
    End;
Begin
     Writeln(‘введите размерность лабиринта’);
     Read(M,N);
     Writeln(‘введите лабиринт: 0-проход, 1-стена’);
     For X := 1 to M  do For Y := 1 to N do read(Mas[X, Y]);
     WriteLn('введите координаты Воробья');
     ReadLn(XS, YS);
     WriteLn('введите координаты клада');
     ReadLn(XF, YF);
{если координаты начальной или конечной точек пути выпадают на стену, то выводится ошибка}
     If (Mas[XS, YS] = 1) or (Mas[XF, YF] = 1) then Begin
                                                                            WriteLn('Компас не исправен!!!');
                                                                           ReadLn;
                                                                           Halt;  End;
{прямая волна}
     MasM[XS, YS] := 1; 
     K := 1;
     Repeat
           K := K + 1;
           For X := 1 to M do For Y := 1 to N do
               If MasM[X, Y] = K - 1 then
                 Begin
                   If (Y <N) and (MasM[X, Y + 1] = 0) and (Mas[X, Y+1] = 0) 
                     Then MasM[X, Y+1] := K;
                   If (Y >1) and (MasM[X, Y-1] = 0) and (Mas[X, Y-1] = 0) 
                     Then MasM[X, Y-1] := K;
                   If (X <M)and (MasM[X+1, Y] = 0) and (Mas[X+1, Y] = 0) 
                     Then MasM[X+1, Y] := K;
                   If (X >1) and (MasM[X-1, Y] = 0) and (Mas[X-1, Y] = 0) 
                      Then MasM[X-1, Y] := K;
                  End;
         If К = M*N then Begin  WriteLn('Клад не достижим!!!'); ReadLn; Halt;  End;
     Until MasM[XF, YF] >0;
    {обратная волна} 
    K := K - 1; step:=K;  X := XF;  Y := YF;   Mas[XF, YF] := 4;
     Repeat
           Next(X, Y);
           Mas[X, Y] := 3;      K := K - 1;
     Until (X = XS) and (Y = YS);
     Mas[XS, YS] := 2;
{вывод результата}
     WriteLn;
     For X := 1 to M do  Begin
              For Y := 1 to N do Write(Mas[X, Y], ' ');
              WriteLn;
                                       End;
     Writeln;
     WriteLn('длина пути: ', step);
     ReadLn;
End.

и не совсем понятен принцип работы обратной волны.Заранее спасибо за любую помощь.

[BDA]

В Masm хранится волна. "Обратная волна" - для клетки с кладом с номером K нужно найти прилегающую клетку с номером K - 1 и перейти в неё, продолжать, пока не дойдем до места старта.

[Adelia]

Зачем мы обозначаем координаты воробья за 1 MasM[XS, YS] := 1.
если у нас по уловию 1 - это стена?

[BDA]

Это обозначение никак не связано с условием. Элементы каждого уровня волны имеют свой порядковый номер. Для лучшего понимания нарисуйте простенький лабиринт на листочке (стенки - закрашенные клетки). Затем поставьте в любую клетку единичку и от неё начните распространять волну, нумеруя клетки.

[Serge_Bliznykov]

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

Визуализация поиска пути разными алгоритмами

p.s. всё на английском...

[Adelia]

спасибо за ссылку))