Форум программистов, компьютерный форум, киберфорум
Наши страницы
Pascal ABC
Войти
Регистрация
Восстановить пароль
 
laric11
0 / 0 / 0
Регистрация: 01.10.2017
Сообщений: 1
1

Алгоритм Дейкстры на графе

01.10.2017, 05:05. Просмотров 400. Ответов 0
Метки нет (Все метки)

Есть задача по информатике
«Гуляющий кубик»
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Ограничение по времени тестирования: 2 секунды на один тест.
Гарри Поттеру на день рождения подарили волшебный кубик. Кубик находится на
некоторой клетке обычной шахматной доски размером 8×8. Кубик полностью закрывает
собой ровно одну клетку доски, т.е. размер ребра кубика равен размеру стороны клетки
доски. На каждой стороне кубика записано какое-то целое число N (0 ≤ N ≤ 1000). На
разных сторонах кубика могут быть различные числа.
Из начальной клетки кубик с помощью заклинания перемещается по доске путем его
поворота через соответствующее ребро на соседнюю клетку. Каждому возможному пути
перемещения кубика из начальной клетки в конечную можно поставить в соответствие
сумму чисел, побывавших на его нижней грани, при этом каждое число добавляется
столько раз, сколько оно появлялось на нижней грани кубика. Числа, соответствующие
начальному и конечному положению кубика, также суммируются. Путь кубика считается
оптимальным, если при достижении конечной клетки названная сумма оказывается
минимальной.
Требуется написать программу, определяющую путь между двумя заданными клетками,
которому будет соответствовать минимальная сумма чисел, побывавших на нижней грани
кубика. Начальная и конечная клетки различны.
Формат входных данных:
Во входном файле INPUT.TXT в первой строке через пробел записаны координаты
начальной и конечной клеток в следующем формате: первый символ – буква от ‘a’ до ‘h’
включительно, определяющая номер столбца на шахматной доске, второй – цифра от 1 до
8 включительно, определяющая номер строки.
Во второй строке файла находятся 6 чисел, которые записаны на гранях кубика
спереди, сзади, сверху, справа, снизу и слева соответственно. Числа в строке разделены
пробелами.
Формат выходных данных:
Выходной файл OUTPUT.TXT состоит из двух строк. В первой строке записана
минимальная сумма чисел пути. Во второй строке выведен сам оптимальный путь
перемещения кубика или один из возможных путей, если их несколько. Путь представляет
собой последовательность координат клеток на шахматной доске, отображающих процесс
перемещения кубика. Он начинается в начальной клетке и заканчивается в конечной. Все
координаты клеток должны быть представлены в том же формате, что и во входном файле
и разделены пробелами.
Пример файлов входных и выходных данных:
OUTPUT.TXT INPUT.TXT
е2 e3 5
0 8 1 2 1 1 e2 d2 d1 e1 e2 e3

Искал в интернете там только про уже готовое поле и изменять каждое число очень сложно. Подскажите пожалуйста.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.10.2017, 05:05
Ответы с готовыми решениями:

Алгоритм Дейкстры
Помогите с программой. Алгоритм Дейкстры. Значения даны для примера. Их нужно...

Алгоритм Дейкстры
Пожалуйста, можете указать где у меня ошибка(лучше всего укажите как её...

Поиск кратчайшего пути (алгоритм Дейкстры) с наименьшим максимальным ребром
Есть классическая реализация Дейкстры, пытаюсь добавить условие: если есть...

Реализовать алгоритм Дейкстры от первой вершины до всех остальных - найти ошибку
помогите с програмой program Dijkstra; uses crt; const V=6; inf=100000;...

Алгоритм Дейкстры
поиск минимального пути.Посмотрите что не так,не выводит минимальный...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.10.2017, 05:05

Алгоритм Дейкстры
Помогите доделать алгоритм Дейкстри.Проблема в том что надо сделать так что бы...

алгоритм Дейкстры
please

Как применить алгоритм Дейкстры
Задача тут тик вот что я сделал: var N:integer; E:integer; ...


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

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

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