Нужен алгоритм.

← →
Smart (2008-05-27 21:06) [0]

Ребята, пожалуйста помогите, вот такая вот задача:

В замке стоунхендж юный принц не поладил со своей гувернанткой в комнате, где они завтракали. Для избегания наказания принц решил спрятаться в одной из комнат замка, двигаясь из комнаты в комнату принц обязательно закрывал на ключ дверь, через которую он прошел, после чего ни он, ни гувернантка не могли воспользоваться этой дверью. Через любую комнату, в том числе и через ту в которой находится гувернантка, принц может проходить несколько раз, если это позволяет еще не запереть им двери. Изначально все двери замка не заперты.
Между двумя комнатами замкам не более 1 двери общее кол-во дверей не превосходит 5 000.
Гувернантка начинает искать принца только после того, как он спрятался. Избежать наказания принц может только в том случае, если гувернантка, проходя через оставшиеся не запертые двери, не сумеет попасть в комнату, где он спрятался.
Требуется написать программу, которая определяет, сможет ли принц спрятаться от гувернантки и, если укрыться удается, то предлагает ему любой из возможных путей спасения.

Входные данные
Во входном файле castle.in содержится план замка.
В первой строке входного файла находится натуральное число N (1<N<1 000) – количество комнат.
Во второй строке входного файла содержится нат. Число K (1<=K<=N) – номер комнаты, в которой принц и гувернантка завтракали.
В последующих N строках содержатся списки смежных комнат: в i-ой строке перечислены через пробел номера комнат, смежных с i-ой комнатой. Каждая такая строка заканчивается нулем.

Выходные данные
Выходной файл с именем castle.out должен содержать следующую информацию. Если принц не сможет избежать наказания, в единственной строке файла выводится сообщение No. В противоположном случае, в первой строке файла выводится сообщение Yes, во второй строке – кол-во дверей, закрытых принцем, а в третьей строке – последовательность номеров комнат, раздельных пробелами, в которых побывал принц.

Пример входного файла
4
1
2 4 0
4 1 3 0
2 4 0
1 2 3 0

Пример выходного файла для приведенного примера входного файла
Yes
3
1 4 2 3

← →
имя (2008-05-27 21:30) [1]

Удалено модератором

← →
KSergey © (2008-05-28 08:08) [2]

Есть два встречных вопроса:
а) в каком конкретно месте надо помочь?
б) если конкретного места не имеется - необходимо озвучить припасенную сумму с уточнением валюты. Авось кто и отыщется.

← →
Smart (2008-05-28 08:25) [3]

Да мне бы алгоритм подсказать)

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

Олимпиада показывает твои знания, а мы лишь можем помочь в каком-то месте кода. Так что - думай сам! =) И, кстати, удачи! :))

Нужен алгоритм. Найти похожие ветки