Сообщение Re: Заяц от 24.10.2016 17:20
Изменено 24.10.2016 17:21 Буравчик
Здравствуйте, olimp_20, Вы писали:
_>В небольшой посадке живет заяц. Выскочив из норы и бегая по снегу, он оставил следы. Определить где находится заяц.
_>Входные данные
_>Карта движения зайца задана N (1≤N≤100) строками, которые содержат последовательность заглавных латинских букв первая буква откуда следующие куда.
_>Выходные данные
_>Выведите последовательность букв в столбик в порядке возрастания, которые указывают возможное местоположение зайца, если карта не может быть движением зайца вывести NO SOLUTION.
_>Пример
_>10
_>B C D K M A
_>C D K L
_>D L R
_>K L Q N M
_>M N A
_>A P N
_>N P
_>Q P R L
_>L R
_>R P
_>Ответ
_>B
_>L
Похоже здесь описан граф.
Анлийские буквы — вершины.
Каждая строчка — это список ребер, выходяших из вершины, которая стоит в начале строки.
Т.е. строка "M N A" означает наличие в графе ребер M->N и M->A
Таким образом мы можем построить весь граф.
_>2) "Выведите последовательность букв ... в порядке возрастания" — означает, что предварительно выполняется топологическая сортировка, где L получает меньший номер, чем А, хотя обе вершины находятся в одном цикле?
Думаю так: по заданному графу нужно определить, можно ли обойти граф по всем ребрам, проходя каждое ребро строго по одному разу. Т.е. определить наличие Эйлерова пути
Конец такого пути и будет ответом. А также начало пути, если граф неориентирован.
Или ответом будут все вершины, если есть эйлеров цикл.
_>3) NO SOLUTION — ответ, когда не существует пути, по которому можно пройти все вершины (в примере — выйдя из В можно посетить все вершины)?
Если пути нет, то NO SOLUTION
_>В небольшой посадке живет заяц. Выскочив из норы и бегая по снегу, он оставил следы. Определить где находится заяц.
_>Входные данные
_>Карта движения зайца задана N (1≤N≤100) строками, которые содержат последовательность заглавных латинских букв первая буква откуда следующие куда.
_>Выходные данные
_>Выведите последовательность букв в столбик в порядке возрастания, которые указывают возможное местоположение зайца, если карта не может быть движением зайца вывести NO SOLUTION.
_>Пример
_>10
_>B C D K M A
_>C D K L
_>D L R
_>K L Q N M
_>M N A
_>A P N
_>N P
_>Q P R L
_>L R
_>R P
_>Ответ
_>B
_>L
Похоже здесь описан граф.
Анлийские буквы — вершины.
Каждая строчка — это список ребер, выходяших из вершины, которая стоит в начале строки.
Т.е. строка "M N A" означает наличие в графе ребер M->N и M->A
Таким образом мы можем построить весь граф.
_>2) "Выведите последовательность букв ... в порядке возрастания" — означает, что предварительно выполняется топологическая сортировка, где L получает меньший номер, чем А, хотя обе вершины находятся в одном цикле?
Думаю так: по заданному графу нужно определить, можно ли обойти граф по всем ребрам, проходя каждое ребро строго по одному разу. Т.е. определить наличие Эйлерова пути
Конец такого пути и будет ответом. А также начало пути, если граф неориентирован.
Или ответом будут все вершины, если есть эйлеров цикл.
_>3) NO SOLUTION — ответ, когда не существует пути, по которому можно пройти все вершины (в примере — выйдя из В можно посетить все вершины)?
Если пути нет, то NO SOLUTION
Re: Заяц
Здравствуйте, olimp_20, Вы писали:
_>Пример
_>10
_>B C D K M A
_>C D K L
_>D L R
_>K L Q N M
_>M N A
_>A P N
_>N P
_>Q P R L
_>L R
_>R P
_>Ответ
_>B
_>L
Похоже здесь описан граф.
Анлийские буквы — вершины.
Каждая строчка — это список ребер, выходяших из вершины, которая стоит в начале строки.
Т.е. строка "M N A" означает наличие в графе ребер M->N и M->A
Таким образом мы можем построить весь граф.
_>2) "Выведите последовательность букв ... в порядке возрастания" — означает, что предварительно выполняется топологическая сортировка, где L получает меньший номер, чем А, хотя обе вершины находятся в одном цикле?
Думаю так: по заданному графу нужно определить, можно ли обойти граф по всем ребрам, проходя каждое ребро строго по одному разу. Т.е. определить наличие Эйлерова пути
Конец такого пути и будет ответом. А также начало пути, если граф неориентирован.
Или ответом будут все вершины, если есть эйлеров цикл.
_>3) NO SOLUTION — ответ, когда не существует пути, по которому можно пройти все вершины (в примере — выйдя из В можно посетить все вершины)?
Если пути нет, то NO SOLUTION
_>Пример
_>10
_>B C D K M A
_>C D K L
_>D L R
_>K L Q N M
_>M N A
_>A P N
_>N P
_>Q P R L
_>L R
_>R P
_>Ответ
_>B
_>L
Похоже здесь описан граф.
Анлийские буквы — вершины.
Каждая строчка — это список ребер, выходяших из вершины, которая стоит в начале строки.
Т.е. строка "M N A" означает наличие в графе ребер M->N и M->A
Таким образом мы можем построить весь граф.
_>2) "Выведите последовательность букв ... в порядке возрастания" — означает, что предварительно выполняется топологическая сортировка, где L получает меньший номер, чем А, хотя обе вершины находятся в одном цикле?
Думаю так: по заданному графу нужно определить, можно ли обойти граф по всем ребрам, проходя каждое ребро строго по одному разу. Т.е. определить наличие Эйлерова пути
Конец такого пути и будет ответом. А также начало пути, если граф неориентирован.
Или ответом будут все вершины, если есть эйлеров цикл.
_>3) NO SOLUTION — ответ, когда не существует пути, по которому можно пройти все вершины (в примере — выйдя из В можно посетить все вершины)?
Если пути нет, то NO SOLUTION