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

  для  6 – 4,  для  7 – 40, для  8 – 92, для  9 – 352,  для 10 - 724

  для 11 – 2680,  для 12 - 14200  }

Uses Crt;

Var

  Ch: array[1..20] of char;

  {символьное обозначение вертикалей доски}

  Sc: array[1..20] of integer;{счетчики для строк (положения ферзей)}

  N, i,j, k,m: integer;

  F: text; {для найденных позиций}

  Poz: array [1..20] of integer; 

  {индекс-номер строки, значение-номер позиции (столбца), где ферзь}

  Flag: boolean;

Procedure OutPoz; {выдача позиции}

Begin

  For i:=1 to N do

  Write(F, Ch[i],Poz[i],'  ');

  j:=j+1; {количество позиций}

  WriteLn(F)

End;

Begin  {начало основной программы}

  ClrScr;

  Write('Введите размер доски (до 12) ');

  ReadLn(N);

  if (N<1) or (N>12) then

  begin

  WriteLn('  Недопустимый размер, до новых встреч!');

  ReadLn;

  Halt

  end;

  j:=ord('a');

  For i:=1 to N do {присвоение обозначений столбцам доски}

  begin

  Ch[i]:=Chr(j);

  j:=j+1

  end;

  j:=0;  {счетчик общего количества позиций}

  Assign(F,'out. txt');

  Rewrite(F);

  WriteLn(F,'  Позиции для ',N,' ферзей:');

  For i:=1 to N do Sc[i]:=0; {счетчики позиций(столбцов) по строкам}

  k:=1; {номер строки}

  While k>0 do {для перебора - стек по строкам}

  begin

  Sc[k]:=Sc[k]+1;  {номер столбца}

  While Sc[k]<=N do

  begin

  m:=Sc[k];

  {далее: можно ли ставить очередного ферзя на клетку (k, m)?}

  Flag:=false;

  For i:=1 to  k-1 do

  if (m=Poz[i]) or (Abs(k-i)=Abs(m-Poz[i])) then

  {клетка (k, m) в одном столбце или

  на одной диагонали с i-м ферзем}

  begin

  Flag:=true;

  Break

  end;

  if Flag then {клетка (k, m) под боем предыдущих ферзей}

  begin

  Sc[k]:=Sc[k]+1;  {следующая позиция в строке}

  if Sc[k]<=N then Continue {на анализ следующей позиции}

  else Break

  {ферзь в строке k разместить не удалось,

  отступаем на предыдущую строку}

  end

  else {клетка (k, m) пригодна для следующего ферзя}

  begin

  Poz[k]:=m;

  if k=N then OutPoz

  {размещен последний ферзь, вывод расположения ферзей}

  else k:=k+2;

  { после следующего оператора Break будет k:=k-1}

  Break

  end;

  end;  {конец цикла While по столбцам строки k}

  Sc[k]:=0; {может выполняться при k=N+1}

  k:=k-1;

  end;  {конец цикла While по строкам}

  WriteLn(F,'  Общее количество позиций ', j);

  Close(F);

  WriteLn

End.

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

Рассмотрим еще одну распространенную задачу, для решения которой используется поиск в глубину [2].

Грядки. Прямоугольный садовый участок шириной N и длиной M метров разбит на квадраты со стороной 1 метр. На этом участке вскопаны грядки. Грядкой называется совокупность квадратов, удовлетворяющая таким условиям:

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

Подсчитайте количество грядок на садовом участке.

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

Вывод в файл OUTPUT. TXT. Вывести одно число - количество грядок на участке.

Ограничения: 1 ≤ N, M ≤ 200.

Пример

Ввод

5 10

##......#.

.#..#...#.

.###....#.

..##....#.

........#.

Вывод

3

В терминах компьютерной графики мы имеем дело с 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 раза в вызывающей процедуре Paint}

  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.

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

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

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

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

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

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

Пример

Ввод

5

.....

...##

..#..

..###

.....

Вывод

198

1.2. Скобки (4)

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

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

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

(())

([])

()()

()[]

[()]

[[]]

[]()

[][]

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

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

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