Форум программистов, компьютерный форум CyberForum.ru

Острова в море - C++

Восстановить пароль Регистрация
 
nikityonok
Сообщений: n/a
02.12.2010, 21:15     Острова в море #1
Помогите пожалуйста сделать эту прогу, либо дайте подсказки, как можно сделать.
Нужно сделать прогу с помощь ю перебора с возвратом.
Задача чем-то похожа на японский кроссворд.


Международная олимпиада по информатике 1992 года
г. Бонн, Германия,
12—21 июля 1992 г.
ЗАДАЧА ПЕРВОГО ТУРА
"ОСТРОВА В МОРЕ"
Расположение островов в море представлено с помощью сетки размером N*N. Каждый остров обозначается символом "*" в узле этой сетки. Задача заключается в том, чтобы восстановить карту морских островов по закодированной информации о распределении островов по горизонталям и вертика лям. Для иллюстрации принципа кодирования рас смотрим следующую карту и соответствующие ей коды:
* _ * * _ _ 1 2
_ * * * _ * 3 1
* _ * _ * _ 1 1 1
_ * * * * * 5
* * _ * _ * 2 1 1
_ _ _ * _ _ 1
1 1 4 2 2 1
1 2 3 2
1

Числа справа от карты на этом рисунке явля ются кодами и представляют порядок и размер групп островов в соответствующих горизонталях сетки.
Например, цифры "1 2" в первой строке означают, что первая горизонталь содержит группу из одного острова, за которой следует группа из двух остро вов. Слева и справа от каждой группы островов рас положено море произвольной протяженности. Ана логично, последовательность "1 1 1" в первом столбце под картой островов означает, что первая вертикаль содержит три группы островов, в каждой из которых один остров, и т. д.
Постановка задачи
Написать программу, которая выполняет сле дующие действия (шаги) до тех пор, пока данный входной файл, содержащий несколько независимых блоков информации, не будет прочитан полностью:
1. Считывает очередной блок информации из входного ASCII файла (структура этого файла при ведена в примере 1 и отображает его на экране.
П р и м е р 1
6
1 2 0 - строка для первой горизонтали
3 1 0
1 1 1 0
5 0
2 1 1 0
1 0
1 1 1 0 - строка для первого стобца
1 2 0
4 0
2 3 0
2 3 0
2 0
1 2 0

П р и м е р 2
Блок входной
информации Решение
4 Столбцы 12 3 4
0 Строка 1
1 0 Строка 2 *
2 0 Строка 3 * *
0 Строка 4
0
1 0
2 0
0

П р и м е р 3
2
0
0
2 0
2 0
Для этих данных не существует карты.

П р и м е р 4
2
1 0
1 0
1 0
1 0
Этим данным удовлетворяют две различные карты.

Каждый блок информации начинается с размеров квадратной сетки, за которыми следует кодовая информация о горизонтальном и вертикальном рас*пределении островов. Код для каждой отдельной го ризонтали и вертикали является отдельной строкой файла и представляет собой последовательность чи сел, разделенных пробелами. Заканчивается каждая строка нулем. При этом сначала идет информация о всех горизонталях, а затем — о всех вертикалях.
2. Восстанавливает карту (или все карты в слу чае не единственного решения, как в примере 4) и отображает ее (их) на экране.
3. Добавляет карту (карты) в конец выходного ASCII файла. Каждое пустое место в сетке должно быть представлено двумя пробелами, а каждый ост ров — символом "* " (звездочка и пробел). В случае неоднозначного решения различные карты должны быть отделены друг от друга пустой строкой. Если карту восстановить невозможно, в соответствую щей строке выходного файла написать "nо mар". Ре шения, относящиеся к различным блокам информации входного файла, должны быть отделены в выходном файле строкой с надписью "next problem ".
Технические ограничения
1. N должно быть не меньше 1 и не больше 8.
2. Результирующая программа должна быть по мещена в текстовый ASCII файл с именем C:\IOI\DAY- l\413-PROG.xxx. Расширение .ххх для PASCAL - .PAS, для С - .С, для BASIC -.BAS, для LOGO - .LOG.
3. Имя входного ASCII файла должно быть C\IOI\DAY-1\413-SEAS.IN.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.12.2010, 21:15     Острова в море
Посмотрите здесь:

Надо найти "острова" на квадратной матрице C++
Интересная программа про "острова в море" C (СИ)
C# Острова в матрице (Единицы - это острова, а нули - море)
Острова и очередь C++
Есть острова и мосты между ними. Нужно обойти все острова, побывав на каждом мосту по разу Delphi
Найти кол-во островов на море C++
C++ Вычислить давление в море на заданной глубине
3D модель острова

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 10:42. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru