Поиск в ширину. Волновой алгоритм

Поиск в ширину также встречался в задаче поиска путей на графе [9]. Есть множество других задач, для решения которых используется этот же подход. Если при поиске в глубину последовательно достраивается единственное частичное решение, то при поиске в ширину происходит переход от одного частичного решения к другому. Поиск решения производится широким фронтом. Типичным примером поиска в ширину является алгоритм Дейкстры поиска кратчайшего пути на графе.

Рассмотрим схему поиска в ширину на следующем примере.

Игра Lines. В таблице из N строк и N столбцов некоторые клетки заняты шариками, другие свободны. Выбран шарик, который нужно переместить, и место, куда его нужно переместить. Выбранный шарик за один шаг перемещается в соседнюю по горизонтали или вертикали свободную клетку. Требуется выяснить, возможно ли переместить шарик из начальной клетки в заданную, и, если возможно, то найти путь из наименьшего количества шагов.

Ввод из файла INPUT.TXT. В первой строке находится число N, в следующих N строках - по N символов. Символом точки обозначена свободная клетка, латинской заглавной O - шарик, @ - исходное положение шарика, который должен двигаться, латинской заглавной X - конечное положение шарика.

Вывод в файл OUTUT.TXT. В первой строке выводится Y, если движение возможно, или N, если нет. Если движение возможно, далее следует N строк по N символов - как и на вводе, но буква X, а также все точки по пути заменяются плюсами.

Ограничения: 2 ≤ N ≤ 40, время 1 с.

Примеры

Ввод 1 Ввод 2 Ввод 3

5 5 5

.... X.. X..... X.

. O O O O..........

..... O O O O O O. O O O

O O O O...........

@...... @...... @

Вывод 1 Вывод 2 Вывод 3

Y N Y

+ + + + +.. + +.

+ O O O O. + +..

+ + + + + O + O O O

O O O O +. + + + +

@ + + + +.... @

Для решения задачи используется так называемый волновой алгоритм. В целях удобства организуем барьер, объявив двумерный массив от 0 до N+1 по каждому измерению. Во все барьерные клетки занесем признаки занятости в виде символов ‘O’. Это избавит нас от необходимости проверять каждый раз, находимся ли мы на краю поля.

В начальную клетку поместим числовую метку 0. Далее во все соседние с ней пустые клетки занесем метку 1. Во все соседние клетки с меткой 1, помеченные символом ‘.’ как свободные, поместим метку 2 и т. д. Будем считать на каждом шаге количество вновь занесенных меток.

В конце концов, возможна одна из двух ситуаций:

на очередном шаге помечена конечная клетка;

новых меток не появилось.

В первом случае значение метки K равно длине кратчайшего пути из начальной клетки в конечную. Сам путь восстанавливается в обратном направлении. Для конечной клетки находится одна из соседних к ней, имеющая метку K-1. Потом от нее находится следующая клетка с меткой K-2 и так до тех пор, пока не придем в начальную клетку.

Второй случай говорит об отсутствии решения.

Проще всего на каждом шаге находить все клетки с определенным значением метки полным перебором. Такой подход не годится для больших размерностей. В программе Lines, приведенной ниже, клетки, получающие очередные метки, записываются в кольцевую очередь. Выбор клеток из начала очереди обеспечивает просмотр по возрастанию меток.

Program Lines;

Const

Max=150;

Raz=10*Max; {максимальный размер очереди}

Type

Coord=record

X, Y: byte; {координаты}

end;

Me=record

X, Y: byte; {координаты}

Metka: integer; {числовая метка}

end;

Var

i, j, k, Met, p, q: integer;

N, M: integer; {размер участка}

C: array[1..Max, 1..Max] of char;

From: array[0..Max+1, 0..Max+1] of char;

{откуда получена метка: U-сверху, D-снизу, L-слева, R-справа}

{используется также как рабочая карта поля с барьером из 'O'}

Fin, Fout: text;

Och: array[1..Raz] of Me; {кольцевая очередь для поиска в ширину}

BegO, EndO, Count: integer; {для кольцевой очереди}

Nach, Kon: Coord; {начальная и целевая клетки для поиска в ширину}

b: boolean; {признак нахождения решения}

Procedure Zanes(u, v: byte; Var Res: boolean); { занесение в конец кольцевой очереди }

{ (u, v)-текущая клетка, Res=true-дошли до конца }

Begin

if (u=Kon.X) and (v=Kon.Y) then

Res: =true {достижение цели}

else

begin

Res: =false;

EndO: =(EndO mod Raz)+1; {кольцевая очередь}

Och[EndO].X: =u;

Och[EndO].Y: =v;

Och[EndO].Metka: =Met+1; {текущая числовая метка}

Count: =Count+1;

end;

End;

Begin

Assign(Fin, 'input.txt');

Reset(Fin);

ReadLn(Fin, N);

For i: =0 to N+1 do

For j: =0 to N+1 do

From[i, j]: ='O'; {барьер}

For i: =1 to N do

begin

For j: =1 to N do

begin

Read(Fin, C[i, j]);

From[i, j]: =C[i, j]; { сначала копия C }

if From[i, j]='@' then {начало}

begin

Nach.X: =i;

Nach.Y: =j;

From[i, j]: ='O'; {запрет, чтобы не возвращаться}

end;

if From[i, j]='X' then {конец}

begin

Kon.X: =i;

Kon.Y: =j;

From[i, j]: ='.';

end;

end;

ReadLn(Fin); {перевод строки}

end;

Close(Fin);

BegO: =1; {кольцевая очередь для расстановки меток в ширину}

EndO: =1;

Count: =1; {длина очереди}

Och[BegO].Metka: =0;

Och[1].X: =Nach.X; Och[1].Y: =Nach.Y; {начальная точка}

b: =false;

While Count> 0 do

begin

p: =Och[BegO].X;

q: =Och[BegO].Y;

Met: =Och[BegO].Metka;

Och[BegO].X: =0; {для наглядности отладки}

Och[BegO].Y: =0;

BegO: =(BegO mod Raz)+1;

Count: =Count-1; {выбор клетки из начала очереди}

{далее занесение соседних клеток в конец очереди}

if From[p, q+1]='.' then {можно идти направо}

begin

Zanes(p, q+1, b); {занесение в очередь}

From[p, q+1]: ='L'; {пришли слева}

if b then Break; {достигли заданной клетки}

end;

if From[p+1, q]='.' then {можно идти вниз}

begin

Zanes(p+1, q, b); {занесение в очередь}

From[p+1, q]: ='U'; {пришли сверху}

if b then Break; {достигли заданной клетки}

end;

if From[p, q-1]='.' then {можно идти налево}

begin

Zanes(p, q-1, b);

From[p, q-1]: ='R'; {пришли справа}

if b then Break; {достигли заданной клетки}

end;

if From[p-1, q]='.' then {можно идти вверх}

begin

Zanes(p-1, q, b);

From[p-1, q]: ='D'; {пришли снизу}

if b then Break; {достигли заданной клетки}

end;

end; {здесь оказываемся либо при нахождении решения, либо по исчерпанию очереди, когда больше помечать нечего}

Assign(Fout, 'output.txt');

Rewrite(Fout);

if b then {найдено решение}

begin

WriteLn(Fout, 'Y');

p: =Kon.X; q: =Kon.Y; {восстановление от конца}

For i: =1 to Met+1 do {клетку '@' не меняем}

begin

C[p, q]: ='+';

Case From[p, q] of

'U': p: =p-1;

'D': p: =p+1;

'L': q: =q-1;

'R': q: =q+1;

end;

end;

For i: =1 to N do

begin

For j: =1 to N do Write(Fout, C[i, j]);

WriteLn(Fout); {перевод строки}

end;

end

else WriteLn(Fout, 'N');

Close(Fout);

End.