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

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

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

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

17.11.2012, 19:20. Просмотров 1199. Ответов 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 минут
Пробовал релизовать это на поиске в глубину, завис ещё на построении графа...
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.11.2012, 19:20
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Графы и алгоритм Левита (C++):

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

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

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

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

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab () { int s1 = 0; int s2 =...

Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар) - C++
Хочу разработать алгоритм для решения головоломки с подвижными дисками (перестановочная головоломка). Определение. Перестано́вочные...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.11.2012, 19:20
Привет! Вот еще темы с ответами:

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

Графы - C++
Написать на C++ класс, описывающий граф/орграф. Класс должен поддерживать следующую функциональность: • определение числа вершин; ...

Графы - C++
Задача: По системе односторонних дорог определить, есть ли в ней город, из которого можно добраться до каждого из остальных...

Графы - C++
помогите с реализацией алгоритма Дейкстры для нахождения расстояния от узла 1 в каждый узел. матрица весов такая...


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

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

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