Задачи для самостоятельного решения

1.1. Покраска лабиринта (6)

Лабиринт представляет собой квадрат, состоящий из NxN сегментов. Каждый из сегментов может быть либо пустым, либо заполненным монолитной каменной стеной. Гарантируется, что левый верхний и правый нижний сегменты пусты. Лабиринт обнесён сверху, снизу, слева и справа стенами, оставляющими свободными только левый верхний и правый нижний углы. Директор лабиринта решил покрасить стены лабиринта, видимые изнутри (см. рисунок). Помогите ему рассчитать количество краски, необходимой для этого.

Ввод из файла INPUT.TXT. В первой строке находится число N, затем идут N строк по N символов: точка обозначает пустой сегмент, решётка - сегмент со стеной.

Вывод в файл OUTPUT.TXT. Вывести одно число - площадь видимой части внутренних стен лабиринта в квадратных метрах.

Ограничения: 3  N  33, размер сегмента 3 x 3 м, высота стен 3 м, время 1 с.

Пример

Ввод

5

.....

...##

..#..

..###

.....

Вывод

198

1.2. Скобки (5)

При заданном четном N (N  14) перечислить все правильные скобочные формы длины N из скобок ‘(‘, ‘)’, ’[‘, ’]’.

Ввод из файла INPUT.TXT. В единственной строке задается число N.

Вывод в файл OUTPUT.TXT в виде (для N = 4)

(())

([])

()()

()[]

[()]

[[]]

[]()

[][]

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

1.3. Шпионские хлопоты (7)

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

Ввод из файла INPUT.TXT. Первая строка содержит целые числа M, N и L через пробел, где M и N – длина и ширина зоны в клетках, а L – длина стороны клетки. В следующих M строках заданы через пробел N чисел – нулей или единиц. Единицы отмечают занятые психотронами клетки зоны.

Вывод в файл OUTPUT.TXT. Единственная строка содержит результат в виде дробного числа с точностью до одного десятичного знака.

Ограничения: 1 ≤ L ≤ 100; 1 ≤ M ≤ 50; 1 ≤  N ≤ 50; время работы программы до 2 с.

Пример

Ввод

2 3 20

0 1 1

0 1 1

Вывод

222.8

1.4. Реликтовая роща (6)

В заповеднике растет роща реликтовых деревьев. Для их защиты требуется обнести рощу забором. Но для обеспечения доступа к остальной территории заповедника площадь участка, окруженного забором, должна быть минимальной. Деревья растут точно в узлах координатной сетки на расстоянии одного метра друг от друга. Любое из деревьев имеет хотя бы одного соседа (с юга, севера, востока или запада). Забор состоит из блоков длиной в один метр. Чтобы огородить одно дерево необходимо 4 блока забора:

А чтобы огородить такую группу из 9 деревьев нужно 20 блоков:

По заданной конфигурации рощи найти минимально необходимое число блоков для забора.

Ввод. В первой строке записаны через пробел два числа N и K (1  N, K  20)– количество строк и столбцов данных. В следующих N строках содержатся последовательности из K символов (единиц или нулей). Единицей обозначается расположение реликтового дерева, а нулем – его отсутствие в узле координатной сетки.

Вывод. В единственной строке выводится число блоков забора, необходимое для огораживания.

Примеры

Ввод 1 Ввод 2

3 6 5 7

001110 0101010

011011 1111111

011110 0101010

1100011

0111110

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

16 32

1.5. Информатизация садоводства (7)

Дачный участок Степана Петровича имеет форму прямоугольника размером a  b. На участке имеется n построек, причем основание каждой постройки — прямоугольник со сторонами, параллельными сторонам участка.

Вдохновленный успехами соседей, Степан Петрович хочет посадить на своем участке m видов плодовых культур (участок Степана Петровича находится в северной местности, поэтому m = 1 или m = 2). Для каждого вида растений Степан Петрович хочет выделить отдельную прямоугольную грядку со сторонами, параллельными сторонам участка. Само собой, грядки не могут занимать территорию, занятую постройками или другими грядками.

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

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

Ввод. В первой строке входного файла содержатся два целых числа n и m (0 ≤ n ≤ 10; 1 ≤ m ≤ 2). Во второй строке содержатся два целых числа a и b (1 ≤ a, b ≤ 10000). Далее следуют n строк, каждая из которых содержит четыре целых числа x_i,1, y_i,1, x_i,2, y_i,2 –координаты двух противоположных углов постройки (0  x_i,1 < x_i,2  a, 0  y_i,1 < y_i,2   b). Различные постройки не могут пересекаться, но могут касаться друг друга.

Вывод. Необходимо вывести m строк, каждая из которых содержит координаты двух противоположных углов предполагаемой грядки. Координаты должны быть целыми (всегда можно добиться максимальной суммарной площади грядок, располагая их в прямоугольниках с целыми координатами). В случае, если в вашем решении Степану Петровичу следует расположить менее m грядок, необходимо вывести для грядок, которые не следует сажать, строку «0 0 0 0» (см. второй пример).

Примеры

Ввод 1 Ввод 2

2 2 3 2

7 5 4 4

4 2 6 4 0 0 4 1

0 1 2 2 0 1 1 4

3 1 4 4

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

0 2 4 5 1 1 3 4

2 0 7 2 0 0 0 0

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

Поиск в ширину также встречался в задаче поиска путей на графе [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.

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

..... OOOOO O.OOO

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

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

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

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.