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

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

Завдання 1

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

Розв’язання

Задача розв’язується з використанням черги.

Алгоритм

1. Зчитуємо дані з текстового поля до двовимірного масиву

2. Послідовним переглядом виявляємо перший елемент з символом «*».

3. Поміщаємо координати цього елемента в чергу

4. Замінюємо значення елементу на символ « »(пробіл)

5. Додаємо до значення лічильника одиницю

6. Запускаємо цикл, який виконується доки черга не стане порожньою. У циклі виконуємо наступні дії:

а) зчитуємо координати тіла з черги і зчитуємо символ з цієї комірки;

б) якщо цей символ «*», то поміщаємо до черги координати чотирьох сусідів цієї комірки, замінюємо символ на « » і додаємо одиницю до лічильників)

7. Записуємо до текстового поля або надпису значення з лічильника.

Public Class Form1

    Structure S_Queue

        Public x, y As Double

    End Structure

    Dim Queue(100) As S_Queue 'Масив для збереження черги

    Dim First As Integer = 0  'Початок черги

    Dim Last As Integer = -1  'Кінець черги

    Sub PutQueue(ByVal x As Double, ByVal y As Double)

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

        Last += 1

        Queue(Last).x = x

        Queue(Last).y = y

    End Sub

    Function IsEmpty() As Boolean

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

        IsEmpty = First > Last

    End Function

    Function GetQueue(ByRef x As Double, ByRef y As Double) As Boolean

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

        If Not IsEmpty() Then

            x = Queue(First).x

            y = Queue(First).y

            First += 1

            GetQueue = True

        Else

            GetQueue = False

        End If

    End Function

    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click

        Dim mass(10, 10) As Char

        Dim Count As Integer = 0

        Dim x, y As Integer

        Dim s() As String = TextBox1.Text.Split(Chr(10))

        For i = 0 To 9

            For j = 0 To 9

                mass(i, j) = s(i)(j)

            Next

        Next

        For i = 0 To 9

            For j = 0 To 9

                If mass(i, j) = "*" Then

                    PutQueue(i, j)

                    mass(i, j) = " "

                    Count += 1

                End If

            Next

        Next

        While Not IsEmpty()

            GetQueue(x, y)

            If mass(x, y) = "*" Then

                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 += 1

            End If

        End While

        Label2.Text = Count

    End Sub

End Class

Завдання 2

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

Необхідно вивести повідомлення про можливість чи неможливість переходу з вершини A до вершини B.

Наприклад вхідних та вихідних даних:

 Алгоритм розв’язання.

Задачу роз в’яжемо використовуючи пошук у глибину.

1. Створити таблицю суміжності, прочитавши дані про граф з текстового поля.

2. Читаємо з другого текстового поля номер вершини, з якої треба прокласти шлях p.

3. Читаємо з другого текстового поля номер вершини, до якої треба прокласти шлях k.

4. Записуємо в стек номер початкової вершини k.

5. Виконуємо цикл (пункти 6-8), доки стек не порожній.

6. Зчитуємо зі стеку вершину.

7. Якщо ця вершина результуюча, то достроково виходимо з циклу (пункт 9) та виводимо повідомлення про успішний пошук.

8. Поміщаємо до стеку всі вершини, пов’язані з даною, а дану вершину, помічаємо як не пов’язану з іншими.

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

Код мовою VB.NET

Public Class Form1

    Dim stack(100) As Double 'Масив для збереження стеку

    Dim Count As Integer = -1 'Лічильник кількості елементів у стеку

    Sub Push(ByVal x As Double)

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

        Count += 1

        stack(Count) = x

    End Sub

    Function IsEmpty() As Boolean

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

        IsEmpty = Count < 0

    End Function

    Function Pop(ByRef x As Double) As Boolean

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

        If Not IsEmpty() Then

            x = stack(Count)

            Count -= 1

            Pop = True

        Else

            Pop = False

        End If

    End Function

    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click

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

        Count = -1

        'Оголосимо локальні змінні

        Dim n, p, k As Integer

        Dim matr(100, 100) As Integer

        Dim a, b, r, x As Integer

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

        n = Val(TextBox1.Lines(0))

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

        Dim s As String

        For i = 1 To TextBox1.Lines.Count - 1

            s = TextBox1.Lines(i)

            s = s.Trim()

            If s <> "" Then

                r = s.IndexOf(" ")

                a = Val(s.Substring(0, r))

                b = Val(s.Substring(r + 1, s.Length - r - 1))

                matr(a, b) = 1

                matr(b, a) = 1

            End If

        Next

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

        p = Val(TextBox2.Text)

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

        k = Val(TextBox3.Text)

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

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

        Push(p)

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

        Dim flag As Boolean = False

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

        While Not IsEmpty()

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

            Pop(x)

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

            If x = k Then

                flag = True 'Шлях знайдено

                Exit While 'Видодимо з циклу

            End If

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

            For i = 1 To n

                If matr(i, x) = 1 Then

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

                    matr(i, x) = 0 'Помічаємо вершину x як пройдену

                    matr(x, i) = 0 'Помічаємо вершину x як пройдену

                End If

            Next

        End While

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

        If flag Then

            TextBox4.Text = "Шлях є"

        Else

            TextBox4.Text = "Шляху немає"

        End If

    End Sub

End Class

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

Література

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