Метод ветвей и границ. В терминах компьютерной графики мы имеем дело с 4-связными областями, каждую из которых можно обойти ходом шахматной ладьи

Вывод

Ввод

Пример

5 10

##......#.

.#..#...#.

.###....#.

..##....#.

........#.

В терминах компьютерной графики мы имеем дело с 4-связными областями, каждую из которых можно обойти ходом шахматной ладьи. Следует в любом порядке пройти по всем клеткам поля. Если клетка содержит символ ‘#’ (начало новой грядки), нужно заполнить всю 4-связную область символами ‘.’. Как и раньше, удобно организовать барьер, объявив массив клеток с запасом на 1 в каждую сторону и заполнив его перед чтением файла символами ‘.’. Ответом задачи будет количество вызовов извне процедуры перекраски, которая в простейшем случае выглядит так:

Procedure Metka (i,j: integer);

{окраска (пометка грядки) символами '.'}

Begin

if C[i,j] = ’#’ then

begin

C[i,j]:= ‘.’; {пометка клетки (i,j) как пройденной}

Metka (i+1,j);

Metka (i-1,j);

Metka (i,j+1);

Metka (i,j-1);

end;

Можно применять явный стек вместо рекурсивного. Приведем этот вариант программы. Использование динамической памяти позволяет даже в среде Турбо Паскаля увеличить в несколько раз размер поля.

Program Beds;

{заливка с явным стеком}

Const

Max=200;

Type

Stack = array[1..Max*Max] of byte;

{чтобы хватило памяти}

Var

X,Y: ^Stack; {для координат клеток}

i,j: integer;

Top: word; {счетчик для стека}

Fin,Fout: text;

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

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

{карта поля (с барьерами по краям)}

Count: integer; {счетчик количества грядок}

Procedure Pop(Var i,j: integer);

{извлечение из стека очередной клетки грядки}

Begin

i:=X^[Top];

j:=Y^[Top];

Top:=Top-1;

End;

Procedure Push(i,j: integer);

{занесение в стек очередной клетки грядки и ее перекраска}

Begin

if C[i,j]='#' then

{чтобы не проверять 4 раза в вызывающей процедуре Metka}

begin

Top:=Top+1;

X^[Top]:=i;

Y^[Top]:=j;

C[i,j]:='.'; {пометка клетки (i,j) как пройденной}

end;

End;

Procedure Metka(i,j: integer);

{окраска (пометка) грядки символами '.'}

Begin

Top:=0; {начало окраски клеток новой грядки}

Push(i,j);

{занесение клетки (i,j) в стек и перекраска}

While Top>0 do {пока стек непуст}

begin

Pop(i,j);

{извлечение из стека очередной клетки грядки(Pop)}

Push(i+1,j);

Push(i-1,j);

Push(i,j+1);

Push(i,j-1);

end

End;

Begin

For i:=0 to N+1 do {для барьера}

For j:=0 to M+1 do

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

Assign(Fin,'input.txt');

Reset(Fin);

ReadLn(Fin,N,M);

For i:=1 to N do

begin

For j:=1 to M do Read(Fin,C[i,j]);

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

end;

Close(Fin);

New(X); New(Y);

Count:=0;

For i:=1 to N do

For j:=1 to M do

if C[i,j]='#' then {встретили новую грядку}

begin

Count:=Count+1;

Metka(i,j)

end;

Dispose(X);

Dispose(Y);

Assign(Fout,'output.txt');

Rewrite(Fout);

WriteLn(Fout,Count);

Close(Fout);

End.

Метод ветвей и границ является специальным типом поиска с возвратом. Ограничения основываются на предположении, что каждое решение связано с определенной стоимостью. Для применения метода ветвей и границ стоимость должна быть определена для частичных решений. Кроме того для всех частичных решений (a₁, a₂, …, a_k-1) и для всех расширений (a₁, a₂, …, a_k) должно выполняться

F (a₁, a₂, …, a_k-1) ≤ F (a₁, a₂, …, a_k),

где F – функция стоимости. Когда стоимость обладает этим свойством, то при нахождении решения с наименьшей стоимостью можно отбросить частичное решение (a₁, a₂, …, a_k), если его стоимость больше или равна стоимости ранее найденных решений. В большинстве случаев функция стоимости неотрицательна и даже удовлетворяет более сильному требованию

F (a₁, a₂, …, a_k) = F (a₁, a₂, …, a_k-1) + С(a_k),

где С(a_k) ≥ 0 – функция, определенная для всех a_k.

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

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