11. Очередь. Queue(T). Поиск кратчайшего пути в двумерном массиве.

1. Очередь (fifo).

Продолжаем говорить о структурах данных.

Одна из самых полезных структур, которая позволяет описать и запрограммировать огромное количество реальных задач – очередь.

Очередь — это структура данных, представляющая собой специализированным образом организованный список элементов. Доступ к элементам очереди осуществляется по принципу FIFO (First In First Out) — первым пришел, первым вышел. Добавление элемента возможно лишь в конец очереди, выборка — только из начала очереди, при этом выбранный элемент из очереди удаляется.

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

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

Класс Queue<T> представляет обычную очередь, работающую по алгоритму FIFO ("первый вошел - первый вышел").

Произвольный доступ к элементам очереди, как и у стека, невозможен. Новые элементы всегда добавляются в конец очереди. Элемент в начале очереди можно либо получить с удалением, либо прочитать без удаления. Соответственно существуют три основные операции:
Enqueue — добавление
Dequeue — получение с удалением
Peek — чтение без удаления

Сложность алгоритмов добавления и удаления из очереди составляет O(1).

2. Использование очереди. Пример.

Фрагмент кода программы:

class Person
{
    public string Name { get; set; }
}

public static void Main(string[] args)
{
    Queue<int> numbers = new Queue<int>();

    numbers.Enqueue(3); // очередь 3
    numbers.Enqueue(5); // очередь 3, 5
    numbers.Enqueue(8); // очередь 3, 5, 8

    // получаем первый элемент очереди
    int queueElement = numbers.Dequeue(); //теперь очередь 5, 8
    Console.WriteLine(queueElement);

    Queue<Person> persons = new Queue<Person>();
    persons.Enqueue(new Person() { Name = "Tom" });
    persons.Enqueue(new Person() { Name = "Bill" });
    persons.Enqueue(new Person() { Name = "John" });

    // получаем первый элемент без его извлечения
    Person pp = persons.Peek();
    Console.WriteLine(pp.Name);

    Console.WriteLine("Сейчас в очереди "+ persons.Count+" человек");
     
    // теперь в очереди Tom, Bill, John
    foreach (Person p in persons)
    {
        Console.WriteLine(p.Name);
    }

    Console.WriteLine();
    // Извлекаем первый элемент в очереди – Tom
    Person person = persons.Dequeue(); // теперь в очереди Bill, John
    Console.WriteLine(person.Name);
}

3. Поиск кратчайшего пути в двумерном массиве (принц и принцесса).

Открыв глаза, Принц Персии обнаружил, что находится на нижнем уровне подземного лабиринта Джаффара. Лабиринт представляет собой прямоугольную площадку, разбитую на m*n участков. На некоторых участках стоят колонны, поддерживающие потолок, на такие участки Принц заходить не может.

Принц может перемещаться с одного участка на другой соседний свободный участок того же уровня. Любое перемещение занимает у Принца 5 секунд.

На одном из участков нижнего уровня Принца ждет Принцесса. Помогите Принцу найти Принцессу, потратив на это как можно меньше времени.

Входные данные:

В исходном двумерном содержатся m строк, по n символов в каждой: «.» обозначает свободный участок, «о» (английская маленькая буква) обозначает участок с колонной, «1» обозначает свободный участок, в котором оказался Принц в начале своего путешествия, «2» обозначает свободный участок, на котором томится Принцесса. Символы «1» и «2» встречаются во входном файле ровно по одному разу.

Выходные данные:

Выведите минимальное время в секундах, необходимое Принцу, чтобы найти Принцессу или слово «Бесконечность…», если принц не может этого сделать.

Примеры:

Фрагмент кода программы:

class Coordinates
{
    public int X { get; set; }
    public int Y { get; set; }
}

private static string[] _array =
{
    "1....",
    ".o.o.",
    ".oo..",
    "oo...",
    "..o.2"
};

public static void Main(string[] args)
{
    int n = _array.Length;
    int m = _array[0].Length;

    Queue<Coordinates> points = new Queue<Coordinates>();

    int[,] labirint = new int[n + 2, m + 2];

    int xPrincess = 0;
    int yPrincess = 0;

    for (int i = 0; i <= n + 1; i++)
    {
        for (int j = 0; j <= m + 1; j++)
        {
            labirint[i, j] = -1;
        }
    }

    for (int i = 0; i < n; i++)
    {
        string str = _array[i];
        for (int j = 0; j < m; j++)
        {
            if (str[j] == '1')
            {
                labirint[i + 1, j + 1] = -10;
                points.Enqueue(new Coordinates() {X = i + 1, Y = j + 1});
            }
            else if (str[j] == '.')
            {
                labirint[i + 1, j + 1] = 0;
            }
            else if (str[j] == '2')
            {
                xPrincess = i + 1;
                yPrincess = j + 1;
                labirint[i + 1, j + 1] = 0;
            }
        }
    }

    Print(labirint);

    int step = 1;
    int start = 1;
    int end = 1;
    int count = 1;

    while (true)
    {
        for (int i = start; i <= end; i++)
        {
            Coordinates currentCoordinates = points.Dequeue();
            int x = currentCoordinates.X;
            int y = currentCoordinates.Y;
            if (labirint[x - 1, y] == 0)
            {
                labirint[x - 1, y] = step;
                points.Enqueue(new Coordinates() {X = x - 1, Y = y});
                count++;
            }

            if (labirint[x + 1, y] == 0)
            {
                labirint[x + 1, y] = step;
                points.Enqueue(new Coordinates() {X = x + 1, Y = y});
                count++;
            }

            if (labirint[x, y - 1] == 0)
            {
                labirint[x, y - 1] = step;
                points.Enqueue(new Coordinates() {X = x, Y = y - 1});
                count++;
            }

            if (labirint[x, y + 1] == 0)
            {
                labirint[x, y + 1] = step;
                points.Enqueue(new Coordinates() {X = x, Y = y + 1});
                count++;
            }
        }

        if (points.Count == 0)
        {
            break;
        }

        start = end + 1;
        end = count;
        step++;
    }

    Print(labirint);

    if (labirint[xPrincess, yPrincess] == 0)
    {
        Console.WriteLine("Бесконечность...");
    }
    else if (labirint[xPrincess, yPrincess] > 0)
    {
        Console.WriteLine(labirint[xPrincess,yPrincess]*5+" секунд");
    }
    else
    {
        Console.WriteLine("Некорректные данные!"); 
    }
}

private static void Print(int[,] array)
{
    for (int i = 0; i < array.GetLength(0); i++)
    {
        for (int j = 0; j < array.GetLength(1); j++)
        {
            Console.Write(quot;{array[i, j]} \t");
        }

        Console.WriteLine();
    }

    Console.WriteLine();
}

Задание*: Попробуйте самостоятельно вывести в консоль маршрут принца (координаты точек в нужном порядке), по которому должен пройти принц, чтобы спасти принцессу, потратив на это как можно меньше времени.

Итоги занятия.