Введение (стр. 4 )

  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.

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

2.1. Квадратное озеро (6)

Квадратное озеро с островами задается матрицей размером N × N (1 ≤ N ≤ 300). Каждый элемент матрицы содержит либо символ '@' (собака), обозначающий территорию, которая включает часть острова, либо символ '.' (точка), обозначающий участок свободной воды. В левом верхнем углу озера находится квадратный плот размером M × M (1 ≤ M < N) клеток.

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

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

Вывод: файл OUTPUT. TXT должен содержать единственное число — количество необходимых шагов. Если правого нижнего угла достичь невозможно, то в файл выводится No.

Пример

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

7 2  7 3  7 3

.......  .......  .......

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

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

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

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

.......  .......  .......

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

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

10  8  No

2.2. Путь коня (6)

Дана шахматная доска, состоящая из N × N   клеток (2 ≤ N ≤ 300), несколько из них вырезано. Провести ходом коня через невырезанные клетки путь минимальной длины из одной заданной клетки в другую.

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

Вывод в файл OUTPUT. TXT. Если путь построить невозможно, вывести "Impossible", в противном случае вывести такую же карту, как и на входе, но пометить все промежуточные положения коня символом @.

Примеры

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

5  5  5

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

.@@..  ..##.  ..#..

.....  .....  .#...

.....  .....  .....

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

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

...@.  @..@.  Impossible

.@@..  ..##.

....@  .@..@

.....  ..@..

.....  @....

2.3. Остров (10)

Прямоугольный остров имеет кратеры. Требуется соединить каналами ровно два  кратера с океаном так, чтобы общая длина каналов была минимальной. Кратером называется совокупность квадратов, удовлетворяющая таким условиям:

из любого квадрата этого кратера можно  попасть  в  любой другой квадрат этого же кратера, последовательно переходя по кратеру из квадрата в квадрат через их общую сторону; никакие два кратера не пересекаются и не касаются друг друга ни по вертикальной, ни по горизонтальной сторонам квадратов (касание кратеров углами допускается); нет кратеров на границе прямоугольника.

Ввод из файла INPUT. TXT. В первой строке находятся числа N и M  через пробел, далее  идут  N строк по M символов (3 ≤ N, M ≤ 50). Символ X обозначает территорию кратера, точка соответствует  незанятой территории. Других символов в исходном файле нет.

Вывод в файл OUTPUT. TXT. Вывести N строк по M знаков. Каналы  показать символами '*'.

Примеры

Ввод 1  Вывод 1

5 7

.......  ......

.......  ......

..X....  **X...

....X..  ....X*

.......  ......

Ввод 2  Вывод 2

9 13

.............  ........*....

.............  ........*....

..XXXXX......  ..XXXXX**....

..X..X.......  ..X..X..*....

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

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

..XXXXX......  ..XXXXX......

.............  .............

.............  .............

Подсказка. Один из способов решения:

поиском в глубину пометить клетки кратеров числовыми метками (разными для разных кратеров); поиском в ширину (волновой алгоритм) найти два кратчайших пути от разных кратеров до края, определить их общую длину; от каждой свободной клетки поиском  в  ширину найти

кратчайший путь до границы; кратчайший путь до двух разных кратеров

и сложить их длину;

из двух вариантов в пунктах 2 и 3 выбрать лучший.

2.4. Найти кольцо (8)

Прямоугольная комната размером M × N метров с мебелью покрыта квадратными паркетными плитами со стороной один метр. В углу комнаты стоит тяжелый сейф, занимая всю площадь плиты. Под сейф закатилось кольцо с бриллиантом, поэтому решено полностью освободить плиту под сейфом. Для этого нужно переместить сейф на одну из соседних плит путем кантования - поворота в плоскости пола на 90° вокруг одного из своих углов. Соседними считаются плиты, имеющие общую сторону.

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

При повороте сейфа никакая его точка не должна пересекать внутреннюю часть такой плиты, на которой стоит стул или другая мебель.

Матрица  M × N  определяет начальное положение мебели. Каждый элемент матрицы описывает одну паркетную плиту. Сейф находится в левом верхнем углу. Плите с сейфом соответствует символ '#', свободной плите паркета - символ '.' (точка), плите со стулом - символ '@', плите с другой мебелью - символ '*'. Поворот сейфа выполняется за одну минуту, а перестановка стула - за одну секунду. Найти минимальное время в секундах, за которое сейф может быть перемещен.

Ввод из файла INPUT. TXT. В первой строке содержатся числа M и N (2 ≤ M, N ≤ 300), разделенные пробелами. В следующих M строках находится матрица, описывающая комнату, по N подряд идущих символов в строке.

Вывод в файл OUTPUT. TXT. Вывести наименьшее число секунд, необходимых для освобождения плиты под сейфом. Если плиту освободить невозможно, вывести No.

Примеры

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

4 4  4 3  4 2

#...  #.*  #.

....  .@.  .@

@.@.  @**  @*

...@  @.@  @@

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

60  61  No

2.5. Пчела Майа (6)

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

сначала имеется всего одна сота (рис. 1) – это правильное поле первого уровня; затем вокруг соты появляются соседние (рис. 2) – это правильное поле второго уровня; затем строится еще один «ободок» (рис. 3) – это правильное поле третьего уровня, и т. д.

Пчела Майя возвращается в улей. Она живет в одной из сот правильного поля уровня N (2 ≤ N ≤ 20). Для того, чтобы добраться до своей соты (если она не расположена с краю поля), Майе нужно переместиться через другие соты, в которых могут жить как друзья (перемещаться можно), так и враги (перемещаться нельзя). Майя очень устала и хочет добраться до своей соты, пройдя через минимальное число других сот. Свой путь она может начинать с любой дружественной соты, находящейся с краю поля (то есть такой соты, которая не окружена со всех сторон соседними сотами).

Ввод. В первой строке файла INPUT. TXT записано одно число N – уровень правильного поля. В следующих 2N-1 строках содержатся последовательности из символов ‘V’, ‘D’, ‘M’ (‘V’ – сота врага, ‘D’ – сота друга, ‘M’ – сота Майи).

Вывод. В единственной строке файла OUTPUT. TXT выводится минимальное число сот, через которые придется пройти Майе, чтобы попасть в свою соту (своя сота тоже считается), или ноль, если Майе не удастся попасть в свою соту.

Примеры

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

2  3  2

VV  VVV  VV

VMV  VDDV  VMV

VD  VMVDV  VV

  VVDV

  VVD

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

2  6  0

2.6. Шахматы (10)

Шахматная доска состоит из N строк и M столбцов (1 ≤ N, M ≤ 15). Имеется единственный белый король. У черных в распоряжении кони, слоны и ладьи. По заданному расположению фигур требуется взять белым королем все черные фигуры за минимальное число ходов, не находясь при этом под боем.

Ввод. В первой строке находятся числа M и N. В следующих N строках по M символов задано расположение фигур. Имеются  следующие обозначения:

«.» – пустая клетка; «*» – белый король; «K» – черный конь;  «B» – черный слон; «R» – черная ладья.

Белый король в начальной позиции не атакован. Общее число черных фигур не более 14.

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

Ограничения. На одном тесте время счета не должно превышать 6 сек. Максимально допустимая память 256 мгб.

Пример

Ввод

7 9

.........

.........

.........

..R. K.R..

.........

.........

*........

Вывод

9