Реализации алгоритмов/Алгоритм Ли
Алгори́тм волново́й трассиро́вки (волновой алгоритм, алгоритм Ли) — алгоритм поиска пути, алгоритм поиска кратчайшего пути на планарном графе. Принадлежит к алгоритмам, основанным на методах поиска в ширину.
C++
[править]В приведённом примере производится поиск ортогонального пути (считаются 4 соседа клетки). Перед вызовом функции lee() массив grid должен быть заполнен значениями WALL (непроходимая ячейка) и BLANK (проходимая непомеченная ячейка). Если функция lee() возвращает результат true, то в массивах px и py остаются координаты ячеек пути в порядке от стартовой (px[0], py[0]) до финишной (px[len], py[len]).
const int W = 12; // ширина рабочего поля
const int H = 8; // высота рабочего поля
const int WALL = -1; // непроходимая ячейка
const int BLANK = -2; // свободная непомеченная ячейка
int px[W * H], py[W * H]; // координаты ячеек, входящих путь
int len; // длина пути
int grid[H][W]; // рабочее поле
// Перед вызовом lee() массив grid заполнен значениями WALL и BLANK
bool lee(int ax, int ay, int bx, int by) // поиск пути из ячейки (ax, ay) в ячейку (bx, by)
{
int dx[4] = {1, 0, -1, 0}; // смещения, соответствующие соседям ячейки
int dy[4] = {0, 1, 0, -1}; // справа, снизу, слева и сверху
int d, x, y, k;
bool stop;
if (grid[ay][ax] == WALL || grid[by][bx] == WALL) return false; // ячейка (ax, ay) или (bx, by) - стена
// распространение волны
d = 0;
grid[ay][ax] = 0; // стартовая ячейка помечена 0
do {
stop = true; // предполагаем, что все свободные клетки уже помечены
for ( y = 0; y < H; ++y )
for ( x = 0; x < W; ++x )
if ( grid[y][x] == d ) // ячейка (x, y) помечена числом d
{
for ( k = 0; k < 4; ++k ) // проходим по всем непомеченным соседям
{
int iy=y + dy[k], ix = x + dx[k];
if ( iy >= 0 && iy < H && ix >= 0 && ix < W &&
grid[iy][ix] == BLANK )
{
stop = false; // найдены непомеченные клетки
grid[iy][ix] = d + 1; // распространяем волну
}
}
}
d++;
} while ( !stop && grid[by][bx] == BLANK );
if (grid[by][bx] == BLANK) return false; // путь не найден
// восстановление пути
len = grid[by][bx]; // длина кратчайшего пути из (ax, ay) в (bx, by)
x = bx;
y = by;
d = len;
while ( d > 0 )
{
px[d] = x;
py[d] = y; // записываем ячейку (x, y) в путь
d--;
for (k = 0; k < 4; ++k)
{
int iy=y + dy[k], ix = x + dx[k];
if ( iy >= 0 && iy < H && ix >= 0 && ix < W &&
grid[iy][ix] == d)
{
x = x + dx[k];
y = y + dy[k]; // переходим в ячейку, которая на 1 ближе к старту
break;
}
}
}
px[0] = ax;
py[0] = ay; // теперь px[0..len] и py[0..len] - координаты ячеек пути
return true;
}
lee(3, 6, 3, 0); // поиск пути из ячейки (3,6) в ячейку (3, 0) (см. рис.)
Pascal
[править]Данные приводятся в виде (c новой строки)
Размера массива «n m»
Двумерного массива из «@» и " "
Стартовой ячейки «x y»
Финальной ячейки «x y»
На выходе мы получим последовательные координаты в виде «{x, y} {x, y} {x, y} .. {x, y}»
type o=record
dx,dy:integer; {Для лучшего хранения нужны ячеек}
end;
var a:array[1..128,1..128] of integer; {Основной массив (можно заменять на нужный размер}
b,c:array[0..1000] of o; {Массив для ячеек, которые нужно будет пометь как d+1 и потом заменить эти ячейки на ячейки d+1}
n,m,l,t,u,d,s:integer;
finalx,finaly,startx,starty:integer; {стартовая и финальная}
k:char;
procedure read; {Чтения из файла. Стена тут должна быть '@', а пустое место, соответственно, ' '}
var i,j:integer;
begin
readln(n,m);
for i:=1 to n do
begin
for j:=1 to m do
begin
read(k);
if k='@' then a[i,j]:=-1 else a[i,j]:=0; {В массиве это будет -1 и 0 (стена и пустое место)}
end;
readln;
end;
readln(startx,starty); readln(finalx,finaly);
end;
procedure check(i,j:integer); {проверка на соседние ячейки, которые можно пометить, как d+1 для каждой ячейки из массива b}
begin
if (i>1) and (a[i-1,j]=0) then
begin
a[i-1,j]:=d;
inc(l);
c[l].dx:=i-1;
c[l].dy:=j;
end;
if (j>1) and (a[i,j-1]=0) then
begin
a[i,j-1]:=d;
inc(l);
c[l].dx:=i;
c[l].dy:=j-1;
end;
if (i<n) and (a[i+1,j]=0) then
begin
a[i+1,j]:=d;
inc(l);
c[l].dx:=i+1;
c[l].dy:=j;
end;
if (j<m) and (a[i,j+1]=0) then
begin
a[i,j+1]:=d;
inc(l);
c[l].dx:=i;
c[l].dy:=j+1;
end;
end;
procedure findway(i,j:integer); {Поиск финального пути. Идет назад по массиву к стартовой ячейке и записывает ячейку в массив b (уже финальный путь)}
begin
s:=0;
a[startx,starty]:=0;
repeat
dec(d);
if (i>1) and (a[i-1,j]=d) then begin dec(i); inc(s); b[s].dx:=i; b[s].dy:=j; end
else
if (i<n) and (a[i+1,j]=d) then begin inc(i); inc(s); b[s].dx:=i; b[s].dy:=j; end
else
if (j>1) and (a[i,j-1]=d) then begin dec(j); inc(s); b[s].dx:=i; b[s].dy:=j; end
else
if (j<m) and (a[i,j+1]=d) then begin inc(j); inc(s); b[s].dx:=i; b[s].dy:=j; end
else break;
until (i=startx) and (j=starty);
end;
BEGIN
assign(input, 'input.txt'); reset(input);
assign(output, 'output.txt'); rewrite(output);
{---------} read;
b[1].dx:=startx; b[1].dy:=starty;
a[startx,starty]:=-2;
u:=1; d:=0;
repeat
inc(d);
l:=0;
for t:=1 to u do
begin
check(b[t].dx,b[t].dy);
end;
if l=0 then begin write('NO EXIT'); exit; end; {В массив b не добавилась ни одна новая ячейка - путь не найден}
for s:=1 to l do b[s]:=c[s]; {перевод из вспомогательного массива в основной для начала цикла по новому}
u:=l;
until a[finalx,finaly]<>0;
{----------} findway(finalx,finaly);
for d:=s downto 1 do write( '{ ',b[d].dx, ',',b[d].dy,' } ');
end.