Форум программистов, компьютерный форум CyberForum.ru

Минимальная длина маршрута робота - C++

Восстановить пароль Регистрация
 
Stasq329
0 / 0 / 0
Регистрация: 01.05.2014
Сообщений: 15
15.05.2014, 01:04     Минимальная длина маршрута робота #1
Условие
Имеется план местности, разбитой на квадраты, заданный матрицей размера N × M. Каждый квадрат c координатами (i, j) имеет высоту относительно уровня моря, значение которой определяется натуральным числом Aij (нумерация строк и столбцов матрицы A начинается с 1, верхний левый квадрат матрицы имеет координаты (1, 1)). Робот может двигаться только по местности и только параллельно осям ОX и ОY между центрами квадратов. При переходе в соседний квадрат длина подъёма (спуска) равна модулю разности высот квадратов, а длина перемещения из квадрата в квадрат равна величине K. Необходимо найти среди маршрут робота из позиции (X1, Y1) в позицию (X2, Y2) маршрут минимальной длины. Длина маршрута определяется как суммарная длина подъёмов и спусков плюс суммарная длина перемещений из квадрата в квадрат.

Входные данные: in.txt
Первая строка содержит числа N и M (1 ≤ N, M ≤ 1000) — размеры поля, по которому двигается робот (числа разделены одним или несколькими пробелами).
Следующие N строк файла содержат информацию о матрице высот каждого квадрата (строка файла соответствует строке матрицы высот; высоты — целые числа от 1 до 109).

Следующая строка файла — число K.
В последней строке файла задаются координаты начальной и конечной точек движения робота: X1, Y1, X2, Y2 (числа разделяются одним или несколькими пробелами).

Выходные данные: out.txt
Длина кратчайшего маршрута робота.

Пример
in.txt
4 4
5 3 2 6
1 8 4 2
3 2 5 4
2 2 2 2
1
1 1 4 4
out.txt
13
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.05.2014, 01:04     Минимальная длина маршрута робота
Посмотрите здесь:

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

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 23:39. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru