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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
nikityonok
Сообщений: n/a
#1

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

02.12.2010, 21:15. Просмотров 943. Ответов 0
Метки нет (Все метки)

Помогите пожалуйста сделать эту прогу, либо дайте подсказки, как можно сделать.
Нужно сделать прогу с помощь ю перебора с возвратом.
Задача чем-то похожа на японский кроссворд.


Международная олимпиада по информатике 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++
Задача на очередь. Карту, определяющую прямоугольную область моря, представим матрицей с целыми элементами (0 – море, 1 - суша). Островом...

Найти количество островов на море - C++
дана карта в виде массива из 0 и 1, она записана в файле input.txt с таким форматом: в первой строке файла записано 2 числа - кол-во...

Обогнуть остров, выбрав кратчайший путь вокруг острова - C++
Во входном файле находятся: число N, задающее количество вершин многоугольника и далее координаты вершин многоугольника в виде списка x , y...

Вычислить давление в море на заданной глубине - C++
Вычислить давление в море на заданной глубине Помогите пожалуйста с кодом.

вываливается море ошибок при компиляции модуля - C++
Работаю на VS C++ 2015 и столкнулся в проблемой, а именно при создании модулей выводит кучу ошибок ...

Надо найти "острова" на квадратной матрице - C++
Собственно ниже условие и я вроде все понял, но как это сделать... Буду очень благодарен за Вашу помощь.

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.12.2010, 21:15
Привет! Вот еще темы с ответами:

Острова в матрице (Единицы - это острова, а нули - море) - C#
Имеется матрица (n*m) заполненная 1 и 0. Единицы - это острова, а нули - море. Если единицы находятся рядом по горизонтали или вертикали -...

Интересная программа про "острова в море" - C (СИ)
вот суть задачи http://www.nelidovo.edu.ru/olimpiads/informatica/Allolimpiads/meshdunarod/meshdunarod1992.html задача старая, но прошу...

Есть острова и мосты между ними. Нужно обойти все острова, побывав на каждом мосту по разу - Delphi
Задача "Острова и мосты" (задача Эйлера). Есть острова и мосты между ними. Нужно обойти все острова, побывав на каждом мосту по разу. ...

3D модель острова - 3D моделирование
Можете сделать 3d модель


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru