Ключевые слова: программирование, язык программирования, решение, задача, пример, граница, общая, скачать, c++, pascal, visual basic for applications, vba, doc, php, форма, лекции по программированию

Автор: Приходько Максим Александрович

Задачи об общих границах - одни из самых увлекательных и непростых в решении. Одну из таких задач мне пришлось решить в процессе своей работы. Суть задачи состоит в следующем:

1. Территория Российской Федерации разделена на субъекты - крупные территориальные объединения, обладающие собственными органами региональной власти. В свою очередь субъекты делятся на территории - более мелкие территориальные единицы, также обладающие собственными органами местной власти.

2. Известен состав каждого субъекта - перечень составляющих его территорий, а также для каждой территории (и для каждого субъекта в целом) известны все его соседи, т.е. территории (или целые субъекты), имеющие с данной территорией общую границу (см. Рис. 1):

Рис. 1. Два граничащих субъекта

Территориальный состав субъектов хранится в файле regroups.ini в следующем формате:

[subjects]

Республика Адыгея (Адыгея)=1

Республика Алтай=2

Республика Башкортостан=3

Республика Башкортостан - Бирская=3

Республика Башкортостан - Салаватская=3

Республика Башкортостан - Стерлитамакская=3

Республика Башкортостан - Уфимская=3

Республика Бурятия=4

.....................................

В разделе subjects файла regroups.ini последовательно перечисляются субъекты РФ вместе с составляющими их частями. После названия субъекта или одной из его частей стоит символ =, за которым следует код субъекта. Все записи отсортированы по возрастанию кода субъекта.

Субъекты могут граничить между собой как цельные территории, также субъект может граничить с частью другого субъекта и, наконец, две части могут иметь общую границу (Рис. 2).

Рис. 2. Общие границы субъектов и их частей

На Рис. 2 изображены два субъекта (Субъект 1 и Субъект 2), имеющие общую границу. Кроме общей границы двух субъектов каждый из субъектов граничит с каждой из частей второго субъекта, приходящихся на общую границу. Например, Субъект 1 граничит с частями Ч1, Ч7, Ч6, Ч4 второго субъекта (см. Рис. 1). Кроме того, отдельные части двух субъектов также граничат друг с другом. Например, Ч1 с Ч1, Ч1 с Ч7, Ч2 с Ч7 и Ч2 с Ч6 (см. Рис. 2).

Информация об общих границах хранится в файле bounds.ini в следующем формате:

[Республика Башкортостан - Бирская]

Пермский край - Южная=1

Свердловская область - Первоуральская=1

Челябинская область - Кыштымская=1

Республика Башкортостан - Стерлитамакская=1

Республика Татарстан (Татарстан) - Набережно-Челнинская=1

Республика Татарстан (Татарстан) - Нижнекамская=1

Республика Башкортостан - Уфимская=1

Удмуртская Республика=1

[Ярославская область]

Владимирская область=1

Вологодская область=1

Ивановская область=1

Тверская область=1

Костромская область=1

Московская область=1

Разделы обозначены квадратными скобками []. Название раздела соответствует наименованию субъекта или одной из территорий. Содержимое раздела - перечень субъектов и территорий, граничащих с указанной в названии раздела территорией.

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

Рис. 3. Выбор составных частей области

Под "цельностью" понимается возможность из любой точки области попасть в любую другую, не пересекая внешнюю границу области (см. Рис. 4).

Рис. 4. Пример цельной (О1) и разрывной (О2) области

Реальные файлы для проверки работы программы:

http://www.hackmeifyoucan.ru/files/regroups.ini

http://www.hackmeifyoucan.ru/files/bounds.ini