Ответы Mail.ru
Программирование
Android
C/C++
C#
iOS
Java
JavaScript
jQuery
SQL
Perl
PHP
Python
Веб-дизайн
Верстка, CSS, HTML, SVG
Системное администрирование
Другие языки и технологии
Лидеры категории
Лена-пена
М.И.
Y.Nine
•••
Искусственный Интеллект
Искусственный Интеллект
Искусственный Интеллект
Не могу решить задачу по программированию. Не вижу, где здесь графы.
Андрей Матвеев
(202),
закрыт
10 лет назад
Лучший ответ
Антон Афанасьев
(599)
10 лет назад
Вершины - состояния (тек. положения колес, можно задавать числом от 0 до 9999). 10000 вершин.
Ребра - переходы. Из каждого состояния можно перейти в какое-то другое повернув одно из колес либо вправо, либо влево. Из каждого состояния максимум 8 переходов.
В запрещенные состояния ребра не проводим.
Задача свелась к поиску кратчайшего пути на ориентированном графе от стартового состояния до конечного. Т. к. граф не взвешенный можно искать поиском в ширину или в глубину.
Ребра - переходы. Из каждого состояния можно перейти в какое-то другое повернув одно из колес либо вправо, либо влево. Из каждого состояния максимум 8 переходов.
В запрещенные состояния ребра не проводим.
Задача свелась к поиску кратчайшего пути на ориентированном графе от стартового состояния до конечного. Т. к. граф не взвешенный можно искать поиском в ширину или в глубину.
Остальные ответы
Юрий-17
(76476)
10 лет назад
А Вы её и не сможете решить, раз Вам лень даже вручную набрать корректно текст задачи. А графы здесь подразумеваются как переходы между состояниями после нажатия кнопок.
Кэп со стажем
(28502)
10 лет назад
У тебя есть колёса, а ты не видишь графы? Может ты не правильно их принимаешь?
Похожие вопросы
Рассмотрим следующую математическую машину. Цифры от 0 до 9 последовательно (по часовой стрелке) напечатаны по краю каждого колеса. Самые верхние цифры колес образуют четырехзначное целое число. Например, на рисунке колеса образуют число 8056. У каждого колеса есть две кнопки. Нажатие кнопки с левой стрелкой поворачивает колесо на одну цифру по часовой стрелке, а нажатие кнопки с правой стрелкой поворачивает на одну цифру в противоположном направлении. Начальное положение колес формирует целое число Sj S2 S3 S4. Вам задается набор из п запрещенных состояний Fц Fi2 F^ Fi4 (1
Входные данные
Первая строка входных данных содержит целое число N, задающее число тестовых блоков. За ней следует пустая строка.
Первая строка каждого тестового блока содержит начальное состояние колес, задаваемое четырьмя цифрами. Следующая строка содержит конечное состояние. Третья строка содержит целое число п, задающее количество запрещенных состояний. Каждая из следующих п строк содержит запрещенное состояние. Между двумя последовательными тестовыми блоками находится пустая строка.
Выходные данные
Для каждого введенного тестового блока выведите строку, содержащую минимальное необходимое количество нажатий кнопок. Если конечное состояние недостижимо, выведите " -1".