Вам бонус- начислено 1 монета за дневную активность. Сейчас у вас 1 монета

Блокада (решение через графы) кратко

Лекция



Привет, сегодня поговорим про блокада решение через графы , обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое блокада решение через графы , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

Всероссийская командная олимпиада школьников по программированию, 2001

Задание

Государство Флатландия представляет собой прямоугольник размером М x N, состоящий из единичных квадратиков. Флатландия разделена на К провинций (2 <= K <= 100). Каждая провинция представляет собой связное множество квадратиков, то есть из каждой точки провинции можно дойти до любой другой ее точки, при этом разрешается переходить с квадратика на квадратик, только если они имеют общую сторону (общей вершины недостаточно). Во Флатландии нет точки, которая граничила бы более чем с тремя провинциями (то есть четыре квадратика, имеющие общую вершину, не могут принадлежать четырем разным провинциям). Каждая провинция имеет свой символ. Столица Флатландии находится в провинции, имеющей символ А (заглавная латинская буква А). Провинция называется пограничной, если она содержит граничные квадратики. Провинция, в которой находится столица Флатландии, не является пограничной.

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

Чтобы окружить провинцию, требуется захватить все провинции, с которыми она граничит. Две провинции граничат, если существует два квадрата, имеющие общую сторону, один из которых принадлежит первой из них, а другой — второй. Чтобы захватить провинцию, надо чтобы выполнялось одно из двух условий: либо она пограничная, либо граничит с какой-либо уже захваченной провинцией.

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

Блокада (решение через графы)

Ввод

Первая строка содержит М и N (3 <= M, N <= 200). Об этом говорит сайт https://intellect.icu . Следующие М строк содержат N символов каждая и задают карту Флатландии. Символ, находящийся в (i+1)-й строке входного файла на j-м месте, представляет собой символ провинции, которой принадлежит квадратик (i,j). Все символы имеют ASCII-код, больший 32.

Вывод

Выведите в выходной файл единственное число — количество провинций, которые требуется захватить. Если установить блокаду невозможно, выведите «-1».

Пример ввода         Пример вывода
5 6                  4 
BBBBBZ 
BCCCBZ 
BCAbbZ 
BDDDbZ 
33333Z

7 6                  5
ZZZZZZ
NDDDDL
NRCCDL
NBACDL
NNOKKL
NNGGGG
PPPPPP

Решение

Переход к графам осуществляем следующим образом: вершина — область (обозначается символом с возможным кодом от 32 до 255). Ребро отображает смежность двух областей. При вводе исходных данных анализируются две смежные строки: соседние (горизонтально) символы во второй строке и соседние (вертикально) символы первой и второй строк. По этим данным пополняются ребра графа.

Области, смежные с областью A которую нужно блокировать, сразу включаем в список областей, которые нужно захватить. Их количество обозначаем переменной А. Затем алгоритмом Дейкстрынаходим кратчайшие расстояния от внешней области до всех заданных областей.

Если какая-то из областей, смежных с областью A, недостижима, то выводим ответ «-1» и прекращаем работу программы.

Циклом по количеству смежных с А областей:
- все новые вершины, вошедшие в оптимальный путь, добавляем в список всех различных вершин, необходимых для захвата области А;
- обнуляем веса всех ребер, связанных с вершинами, вошедшими в оптимальный путь;
- алгоритмом Дейкстры находим новые кратчайшие расстояния до всех вершин.

После завершения этого цикла выводим количество вершин в созданном списке.

Формальное описание

Blockade()
1. Прочитать из файла карту страны.
2. Создать граф на основании карты (выполнять пп.2.1-2.3):
   2.1.  Инициализировать матрицу смежности нулями.
   2.2.  Для каждого квадрата карты проверить 4 соседние квадрата и если
         соседний квадрат отличается от текущего, то соединить данные
         провинции ребром.
   2.3. Если квадрат лежит на границе карты, то соединить данную провинцию
        с внешней страной.
3. Применить алгоритм Дейкстры для нахождении кратчайшего пути из внешней
   страны в столицу (выполнить пп.3.1.-3.3):
   3.1. Инициализировать расстояния до вершин бесконечностью,
        все метки о нахождении кратчайшего пути нулями.
   3.2. Установить расстояние до стартовой вершины равное 0.
   3.3. Пока не найдены кратчайшие пути для всех вершин, повторять
        пп. 3.3.1-3.3.3:
        3.3.1. Найти вершину, кратчайший путь для которой не найден,
               с минимальным расстоянием.
        3.3.2. Считать, что кратчайший путь для данной вершины найден.
        3.3.3. Обновить расстояния до инцидентных к текущей вершин.
4. Если столица существует и все соседние со столицей вершины достижимы,
   то выполнить пп.4.1.-4.4 количество раз равное количеству вершин
   инцидентных столице, иначе вывести сообщение о невозможности блокады.
   4.1. Удалить ребро между столицей и предшественником в кратчайшем пути.
   4.2. Установить для использованных в кратчайшем маршруте ребер значение
        веса равным 0.
   4.3. Добавить использованные в кратчайшем маршруте вершины к множеству
        захваченных вершин.
   4.4. Применить алгоритм Дейкстры для нахождении кратчайшего пути из
        внешней страны в столицу (выполнить пп.3.1.-3.3).

Рассмотрим решение задачи для второго примера ввода. После инициализации и преобразования отношения инцидентности на карте в связь на графе получим граф из 13 вершин (13 провинций), связанных ребрами следующим образом:

Область  Смежные области 

Z        N D L Внешняя
N        Z D R B O G P Внешняя
D        Z N L R C K
L        D K G Внешняя
R        N D C B
C        D K A R
B        N R A
A        C B O
O        N K A G
K        C D L G O 
G        O K L N P Внешняя
P        N G Внешняя
Внешняя  Z N L G P

К полученному графу трижды (степень вершины-столицы) применяем алгоритм Дейкстры, каждый раз удаляя ребро к вершине-столице, а использованные пути обнуляем.

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

Ищем захваченные вершины и их количество (на графе отмечены красной рамкой). Для данного примера для блокады столицы необходимо захватить 5 провинций: N, D, B, C, O.

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

Из статьи мы узнали кратко, но содержательно про блокада решение через графы
создано: 2014-10-13
обновлено: 2021-12-05
132511



Рейтиг 9 of 10. count vote: 2
Вы довольны ?:


Найди готовое или заработай

С нашими удобными сервисами без комиссии*

Как это работает? | Узнать цену?

Найти исполнителя
$0 / весь год.
  • У вас есть задание, но нет времени его делать
  • Вы хотите найти профессионала для выплнения задания
  • Возможно примерение функции гаранта на сделку
  • Приорететная поддержка
  • идеально подходит для студентов, у которых нет времени для решения заданий
Готовое решение
$0 / весь год.
  • Вы можите продать(исполнителем) или купить(заказчиком) готовое решение
  • Вам предоставят готовое решение
  • Будет предоставлено в минимальные сроки т.к. задание уже готовое
  • Вы получите базовую гарантию 8 дней
  • Вы можете заработать на материалах
  • подходит как для студентов так и для преподавателей
Я исполнитель
$0 / весь год.
  • Вы профессионал своего дела
  • У вас есть опыт и желание зарабатывать
  • Вы хотите помочь в решении задач или написании работ
  • Возможно примерение функции гаранта на сделку
  • подходит для опытных студентов так и для преподавателей



Комментарии


Оставить комментарий
Если у вас есть какое-либо предложение, идея, благодарность или комментарий, не стесняйтесь писать. Мы очень ценим отзывы и рады услышать ваше мнение.
To reply

Алгоритмы и теория алгоритмов

Термины: Алгоритмы и теория алгоритмов