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

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

Примеры

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

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

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

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

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

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

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

5 5 5

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

.OOOO..........

..... OOOOO O.OOO

OOOO...........

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

Y N Y

+++++..++.

+OOOO.++..

+++++ O+OOO

OOOO+.++++

@++++....@

Для решения задачи используется так называемый волновой алгоритм. В целях удобства организуем барьер, объявив двумерный массив от 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.

Дата добавления: 2014-01-11