Лабораторна робота №2.1

Тема. Пошук у ширину та глибину

Мета. Формування умінь розв’язувати задачі на пошук у ширину та глибину з використанням черги та стеку

На рисунку зображено план замку. Замок умовно поділений на m*n клітинок (1≤m≤50, 1≤n≤50). Кожна така клітинка може мати від 0 до 4 стін.

Визначити:

1.      Кількість кімнат у замку.

2.      Площу найбільшої кімнати.

3.      Яку стіну в замку потрібно вилучити, щоб отримати кімнату найбільшої площі.

Формат вхідних даних.
План замку розмістимо у вхідному файлі з іменем input.txt у вигляді послідовності чисел – по одному числу, що характеризує кожну клітинку.

У першому рядку файла записано кількість клітинок у напрямку з півночі на південь.
У другому рядку – кількість клітинок у напрямку із заходу на схід.
У наступних рядка кожна клітинка описується число р (0≤р≤15). Це число р є сумою таких чисел:
1 – якщо клітинка має західну стіну;
2 – якщо клітинка має північну стіну;
4 – якщо клітинка має східну стіну;
8 – якщо клітинка має південну стіну.
Вважається, що внутрішня стіна належить обом клітинкам. Наприклад, південна стіна у клітинці (1, 1) є також північною стіною у клітинці (2, 1).
Замок щонайменше містить дві кімнати.
Вміст вхідного файлу input.txt для замку, зображеного на малюнку:
4
7
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13
Формат вихідних даних.
У вихідному файлі output.txt повинно бути три рядки.
У першому рядку міститься число, що дорівнює кількості кімнат.
У другому рядку – площа найбільшої кімнати (вимірюється кількістю клітинок).
Третій рядок визначає стіну, яку потрібно вилучити: номер рядка і номер стовпчика клітинки, яку потрібно вилучити, і положення цієї стіни в клітинці (N – північ, W – захід, S – південь, E - схід).
Ідея розв’язання.
У задачах на збереження різних типів даних і об’єднання їх в одну зв’язану структуру доцільно використовувати записи. Створимо новий запис Wall, який об’єднує чотири змінних W, N, E, S логічного типу – значення яких свідчитимуть про наявність стіни у певному напрямку (true – клітинка має стіну, false – клітинка не має стіни) і змінну Numb цілочисельного типу – значення якої свідчитиме про належність певній кімнаті.
При зчитуванні даних заповнимо значення для кожної клітинки про положення стін. Для визначення кількості кімнат будемо шукати клітинку, що не належить жодній із кімнат (ai,j.numb=0) – свідчення про наявність ще однієї кімнати, і за допомогою рекурсії обчислюватимемо площу кожної кімнати, заповнюючи клітинки і-ої кімнати числом і (процедура Solve). Серед знайдених площ (масив Square) визначимо максимальну. Для визначення стіни, яку необхідно вилучити, будемо шукати сусідні клітинки із різними значеннями і обчислювати спільну площу кімнат, яким вони належать, вибираючи максимальну. До речі, достатньо перевіряти лише східну і південну сторони.
Код програми на мові Pascal (Delphi)

const size=50;

type

    wall=record

      w,n,e,s:boolean;

      numb:integer;

    end;

var     a:array [1..size, 1..size] of wall;

        m,n,count,numb_x,numb_y:byte;

        st:char;

        square: array [1..size*size] of integer;

        max_square, max_sum:integer;

procedure read_data_init;

var       i,j,t:byte;

begin

     assign (input, 'input.txt');

     reset (input);

     readln (m);

     readln (n);

     fillchar (a, sizeof (a), 0);

     for i:=1 to m do

      for j:=1 to n do

       begin

        read (t);

        if (t>=8) then

                   begin

                    a[i,j].s:=true;

                    dec(t,8);

                   end;

        if (t>=4) then

                   begin

                    a[i,j].e:=true;

                    dec(t,4);

                   end;

        if (t>=2) then

                   begin

                    a[i,j].n:=true;

                    dec(t,2);

                   end;

        if (t=1) then a[i,j].w:=true;

       end;

     close (input);

end;

function max (x,y: integer): integer;

begin

     if x>y then max:=x else max:=y;

end;

procedure run;

var i,j:  byte;

 procedure solve (x,y: byte; var s: integer);

 begin

      a[x,y].numb:=count;

      if (not a[x,y].w) and (a[x,y-1].numb=0) then solve (x,y-1,s);

      if (not a[x,y].e) and (a[x,y+1].numb=0) then solve (x,y+1,s);

      if (not a[x,y].n) and (a[x-1,y].numb=0) then solve (x-1,y,s);

      if (not a[x,y].s) and (a[x+1,y].numb=0) then solve (x+1,y,s);

      inc (s);

 end;

 begin

     max_square:=0;

     for i:=1 to m do

      for j:=1 to n do

       if a[i,j].numb=0 then

                         begin

                          inc (count);

                          solve (i,j,square [count]);

                          max_square:=max(max_square, square [count]);

                         end;

     for i:=1 to m-1 do

      for j:=1 to n-1 do

       begin

        if a[i,j].numb<>a[i,j+1].numb

         then

          if square [a[i,j].numb] + square [a[i,j+1].numb] > max_sum

           then

            begin

             max_sum:=square [a[i,j].numb] + square [a[i,j+1].numb];

             numb_x:=i;

             numb_y:=j;

             st:='E';

            end;

        if a[i,j].numb <> a[i+1,j].numb

         then

          if square [a[i,j].numb] + square [a[i+1,j].numb] > max_sum

           then

            begin

             max_sum:=square [a[i,j].numb] + square [a[i+1,j].numb];

             numb_x:=i;

             numb_y:=j;

             st:='S';

            end;

       end;

end;

procedure write_data;

begin

     assign (output, 'output.txt');

     rewrite (output);

     writeln (count);

     writeln (max_square);

     writeln (numb_x,' ',numb_y,' ',st);

     close (output);

end;

procedure TForm1.Button1Click(Sender: TObject);

begin

    if FileExists('input.txt') then begin

      read_data_init;

      run;

      write_data;

      ShowMessage('Розрахунок закінчено. Відповідь у файлі output.txt');

    end

    else

      ShowMessage('Підготуйте та збережіть до папки проекту файл з вхідними даними input.txt');

end;

Завдання 2
У прямокутній матриці розмірністю 10*10 задано карту місцевості, де пробіл позначає воду, а зірочка – суходіл. Відомо, що на карті зображено острів довільної форми з усіх боків оточений водою. Острів може містити водоймища, площа яких не входить до складу острова. Якщо на озері, що міститься на острові є також острів, то його площу не враховувати в загальну площу острова. Написати програму, яка з текстового поля зчитуватиме карту до масиву та визначатиме площу острова.

Приклад вхідних даних	Результат
****       *  *      ****       * *	12
******     *   *     * * *     *   *     *****      ***        *         ***	24

Розв’язання
Задача розв’язується з використанням черги.
Алгоритм
1. Зчитуємо дані з текстового поля до двовимірного масиву
2. Послідовним переглядом виявляємо перший елемент з символом «*».
3. Поміщаємо координати цього елемента в чергу
4. Замінюємо значення елементу на символ « »(пробіл)
5. Додаємо до значення лічильника одиницю
6. Запускаємо цикл, який виконується доки черга не стане порожньою. У циклі виконуємо наступні дії:
а) зчитуємо координати тіла з черги і зчитуємо символ з цієї комірки;
б) якщо цей символ «*», то поміщаємо до черги координати чотирьох сусідів цієї комірки, замінюємо символ на « » і додаємо одиницю до лічильників)
7. Записуємо до текстового поля або надпису значення з лічильника.
Код програми мовою Pascal (Delphi)

Type

    S_Queue = record

        x, y :integer;

    end;

var Queue:array[0..100] of S_Queue; //Масив для збереження черги

        First :Integer = 0  ;//Початок черги

        Last : Integer = -1  ;//Кінець черги

procedure PutQueue(x,y:integer);

//Процедура запису даних до черги

begin

        Last:=Last + 1;

        Queue[Last].x := x;

        Queue[Last].y := y;

end;

function IsEmpty : Boolean;

//Процедура перевірки черги на порожність

begin

    IsEmpty := First > Last;

end;

procedure GetQueue(var x,y:integer);

//Процедура читання даних з черги

begin

    if not(IsEmpty) then begin

        x := Queue[First].x;

        y := Queue[First].y;

        First :=First + 1;

    end;

end;

procedure TForm1.Button1Click(Sender: TObject);

var Count,i,j:integer;

    x,y:integer;

    mass:array[0..10,0..10] of char;

    s:string;

begin

        First := 0;

        Last := -1;

        Count := 0;

        while Memo1.Lines.Count<10 do Memo1.Lines.Add('          '); //10 пробілів

        for i := 0 to 9 do begin

            s := Memo1.Lines[i];

            if length(s)<10 then s:=s+'          '; //10 пробілів

            for j := 1 to 10 do begin

                mass[i,j]:=s[j];

            end;

        end;

        for i := 0 to 9 do

            for j := 0 to 9 do

                if mass[i, j] = '*' then begin

                    PutQueue(i, j);

                    mass[i, j] := ' ';

                    Count := Count + 1;

                end;

        while not IsEmpty do begin

            GetQueue(x, y);

            if mass[x, y] = '*' then begin

                if x + 1 < 10 then PutQueue(x + 1, y);

                if x - 1 > -1 then PutQueue(x - 1, y);

                if y - 1 > -1 then PutQueue(x, y - 1);

                if y + 1 < 10 then PutQueue(x, y + 1);

                mass[x, y] := ' ';

                Count := Count + 1;

            end;

        end;

        Label2.Caption := IntToStr(Count);

end;

Завдання 3
Граф задано даними з текстового поля. У першому рядку міститься кількість вершин, у наступних рядках попарно вершини, з'єднані між собою ребрами. 
Необхідно вивести повідомлення про можливість чи неможливість переходу з вершини A до вершини B.
Наприклад вхідних та вихідних даних:

Вхідні дані			Результат
Memo1	Edit1	Edit2	Edit3
7 1 2 1 3 1 4 2 3 2 5 2 6 3 5 3 4 5 7 6 7	1	7	Шлях є

 Алгоритм розв’язання.
Задачу роз в’яжемо використовуючи пошук у глибину.
1. Створити таблицю суміжності, прочитавши дані про граф з текстового поля.
2. Читаємо з другого текстового поля номер вершини, з якої треба прокласти шлях p.
3. Читаємо з другого текстового поля номер вершини, до якої треба прокласти шлях k.
4. Записуємо в стек номер початкової вершини k.
5. Виконуємо цикл (пункти 6-8), доки стек не порожній.
6. Зчитуємо зі стеку вершину.
7. Якщо ця вершина результуюча, то достроково виходимо з циклу (пункт 9) та виводимо повідомлення про успішний пошук.
8. Поміщаємо до стеку всі вершини, пов’язані з даною, а дану вершину, помічаємо як не пов’язану з іншими.
9. Виводимо повідомлення про результат пошуку.

Код мовою Pascal (Delphi)

var stack:array[0..100] of integer; //Масив для збереження стеку

    Count:Integer = -1 ;//Лічильник кількості елементів у стеку

procedure Push( x:integer);

//Процедура запису даних до стеку

begin

     Count := Count + 1;

     stack[Count] := x;

end;

function IsEmpty: Boolean;

//функція перевірки стеку на порожність

begin

  IsEmpty := Count < 0;

end;

procedure Pop(var x:integer);

//Процедура читання даних зі стеку

begin

        if not (IsEmpty) Then begin

            x := stack[Count];

            Count := Count - 1;

        end;

end;

procedure TForm1.Button1Click(Sender: TObject);

var n, p, k : Integer;

    matr:array[0..100, 0..100] of Integer;

    a, b, r, x, i, j : Integer;

    s:string;

    flag : Boolean;

begin

        Edit3.Text:='0';

        //Очистимо стек

        Count := -1;

        //Читаємо кількість вузлів графу

        n := StrToInt(Memo1.Lines[0]);

        //Заповнюємо матрицю суміжності

        for i := 1 To Memo1.Lines.Count - 1 do begin

            s := Memo1.Lines[i];

            s := Trim(s);

            while pos('  ', s)<>0 do delete(s,pos('  ',s),1);

            If (s <> '') and (pos(' ',s)<>0) Then begin

                x := pos(' ',s);

                a := StrToInt(copy(s,1,x-1));

                b := StrToInt(copy(s,x+1,Length(s)-x));

                matr[a, b] := 1;

                matr[b, a] := 1;

            end;

        end;

        //Читаємо номер початкової вершини

        p := StrToInt(Edit1.Text);

        //Читаємо номер кінцевої вершини

        k := StrToInt(Edit2.Text);

        //Починаємо пошук шляху

        //Поміщаємо до стеку номер початкової вершини

        Push(p);

        //Локальна змінна-прапорець для відмічання завершення пошуку

        flag:=false;

        //Виконуємо цикл доки стек не порожній

        while not (IsEmpty) do begin

            //Отримуємо зі стеку номер вершини

            Pop(x);

            //Перевіряємо умову досягання результуючої вершини

            if x = k then begin

                flag := True; //Шлях знайдено

                break; //Видодимо з циклу

            end;

            //Шукаємо у матриці суміжності пов"язані з x вершини

            for i := 1 to n do begin

                if matr[i,x] = 1 then begin

                    Push(i);        //Додаємо пов"язану з x вершину до стеку

                    matr[i, x]:= 0; //Помічаємо вершину x як пройдену

                    matr[x, i]:= 0;//Помічаємо вершину x як пройдену

                end;

            end;

        end;

        //Виводимо повідомлення про результат пошуку

        if flag then

            Edit3.Text := 'Шлях є'

        else

            Edit3.Text := 'Шляху немає'

end;

Завдання для самостійного виконання

Література

Караванова, Т.П. Інформатика: методи побудови алгоритмів та їх аналіз: обчисл. алгоритми: навч. посіб. для 9-10 кл. з поглибл. вивч. інформатики. Т.П.Караванова.– К.: Генеза, 2009. – 336 с.: іл. – Бібліогр.: с. 331. (Сторінки 56-68)