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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
_Prof_
1 / 1 / 0
Регистрация: 09.10.2011
Сообщений: 6
#1

Графы и алгоритм Левита - C++

17.11.2012, 19:20. Просмотров 1159. Ответов 0
Метки нет (Все метки)

Доброго времени суток, ув. форумчане! С ровного места возникла проблема: препод дал задачу, но по такому материалу что ещё не проходили, сказал если до воскресения не сделаем- завалит.
Знаю только что нужно делать на графах и алгоритме Левита (или дейкстры), но ни того ни другого не проходили, тоесть знаний по этому у меня покачто ноль. Обьясните пожалуйста как это реализовать.

Условие:

Кликните здесь для просмотра всего текста
Кому из вас не известен знаменитый мультфильм режиссеров Криса Уэйдж и Карлоса Сайдана «Ледниковый период»? Говорят, что после «Ледникового период-2» выйдет «Ледниковый период-3» и в перспективе начнутся работы над созданием нового катастрофического мультфильма «Глобальное потепление-1».

Изюминку сюжета этого фильма составляет момент, когда ненасытная белочка Скрэт попала в Долину Желудей. Помимо огромных пищевых запасов, Скрэт поразила сама местность. Вся долина - это определенное количество холмов, представляют собой полусферы разных радиусов. Конечно, эти симпатичные бугорки пестрят от обилия желудей. Все было бы для Скрэт замечательно, если бы человек своей техногенной деятельностью не спровоцировала глобальное потепление. Очередная катастрофа застала белочку посреди этой широкой долины. Долину начало быстро затапливать и Скрэт в панике прыгала с одного бугорка на другой, ища спасения. Белка, благодаря большим запасам желудей было достаточно энергии чтобы прыгать на любой бугорок, находившийся не далее, чем L метров от бугорка, на котором находилась она сама. Расстояние между бугорками - это расстояние между центрами полусфер независимо от их радиуса. За каждую минуту вода поднималась на высоту H метров. Итак, высота видимой из воды части полусферы также уменьшались на H м в каждую минуту. Скрэт видела, что один за другим исчезают под водой спасательные островки земли. Для того чтобы спастись, она должна быстро добраться крупнейшего бугорка (остривка. Помогите Скрэт найти спасительный путь к самому островка, если за 1 минуту может осуществить только один прыжок. Белочка не может прыгать на островок, сравнялся с поверхностью воды, но всегда успевает покинуть островок, который должен быть затоплен в течение следующей минуты.

Входящие данные: В первой строке входного файла находятся три целых числа N, L, H (2 <= N <= 100, 0 <L <= 1000, 0 <= H <100). В следующих N строках дано по три целых числа Xi, Yi, Ri ((10000 <= Xi, Yi <= 10000, H <Ri <= 10000). Скрэт в начальный момент времени находится на первом острове. Нижние части островков могут перекрываться, но никакие два центра не совпадают.

Исходящие данные: В случае наличия спасительного пути к крупнейшего острова в первую строку выходного файла вывести наименьшее количество прыжков Скрэт, а во вторую строку через пробел вывести номера островов, на которые она должна последовательно прыгать. Если есть несколько самых крупных островов - вывести путь к острову с минимальным номером. В случае отсутствия спасительного пути в единственную строку выходного файла вывести сообщение «The life is fine» без кавычек.


Примеры входящих и исходящих данных:
Кликните здесь для просмотра всего текста

Пример 1:

Входящие:

6 4 1
1 1 1
0 3 2
3 5 1
6 6 4
4 0 2
6 2 3

Исходящие:

3
5 6 4

Пример 2:

Входящие:

2 10 10
0 0 5
10 10 20

Исходящие:

The life is fine


Добавлено через 6 часов 14 минут
Пробовал релизовать это на поиске в глубину, завис ещё на построении графа...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.11.2012, 19:20     Графы и алгоритм Левита
Посмотрите здесь:

Графы. Алгоритм - C++
Определить, можно ли в заданной системе односторонних дорог проехать из города А в город В таким образом, чтобы посетить город С и не...

Графы. Алгоритм Прима - C++
Начал изучать графы и в месте с ними алгоритм Прима. Суть понял, но разобрать(понять) реализацию на с++ не получилось. решил написать...

Графы. Нужно составить алгоритм - C++
Помогите алгоритмизировать задачу! Нужно написать программу способную определить, можно ли в заданной системе односторонних дорог проехать...

Графы, алгоритм Диница (реализовать граф списком смежности) - C++
У меня есть готовая программа по алгоритму Диница, но граф в матричном представлении. Очень нужно чтобы кто-нибудь помог реализовать граф...

Графы - C++
Задан граф матрицей смежности Заданы две вершины, начальная и конечная, требуется найти первую вершину в пути между ними

[C++] графы - C++
Алгоритм фронт фолны в графе Помогите.. Дана матрица Ag (Матрица смежности графа) И координаты начальной вершины i,j и кординаты...

Графы - C++
Имеется сеть автомобильных дорог. Известны расстояния всех участков дорог. Некоторые участки аварийноопасны. Требуется найти путь из пункта...

Графы - C++
помогите пожалуйста написать программу удаления вершины: а)с сохранением связей б)без сохранения связей желательно на с билдер

Графы - C++
Люди скиньте пожалуйста какую нибудь программку на С++ по графам, или дайте ссылку на темку на форему...

графы - C++
помогите пожалуйста начинающему((, вот задачка: Задана система односторонних дорог. Определить, можно ли, построив еще четыре новые...

*Графы* - C++
пожалуйсто помоги мне с программой.умоляю!!! вот тема: реализация различных типов графов и операций над ними. зараннее спасибо.

Графы - C++
Прочитал про обход графа в глубину, посмотрел реализацию, и тут вопрос а как можно использовать этот обход в глубину?


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

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

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