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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Stasq329
0 / 0 / 0
Регистрация: 01.05.2014
Сообщений: 15
#1

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

15.05.2014, 01:04. Просмотров 414. Ответов 0
Метки нет (Все метки)

Условие
Имеется план местности, разбитой на квадраты, заданный матрицей размера 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++
Проложите между А и В такие два маршрута, чтобы в первом сума чисел была 250, а во втором - 350.

Минимальная длина слова в предложении - C++
Здравствуйте, мне надо вывести слово минимальной длины из введенного предложения, вот получилось пока только это, в итоге выводит только...

Минимальная математическая база - C++
Здравствуйте. Заранее прошу прощения за возможный оффтоп, ибо не знал, куда именно можно податься с этим вопросом. Уже давно понял, что без...

Минимальная сумма в столбцах - C++
Вывести надо номер столбца с минимальной суммой,вроде простенько,но что-то туплю Укажите,что не так,я так поняла,дело в условии после...

Функция вывода маршрута - C++
Дан файл, содержащий информацию о маршрутах городского транспорта. Можете помочь написать функции, выдающие количество маршрутов из пункта...

Динамическое программирование, поиск маршрута - C++
Возможно ли организовать поиск пути с препятствием, используя динамическое программирование? Т.е. что то типа лабиринта.

Нахождение маршрута между вершинами - C++
Всем доброго времен суток. Очень нужна помощь в решении задачи Нужно построить маршрут между вершинами неориентированного графа по...

Поиск маршрута от одной точки до другой - C++
Добрый день! подскажите возможно ли разработать скрипт для определения расстояния (маршрута) одной точки до другой? На основе данных яндекс...

Представить в виде двунаправленного списка схему автобусного маршрута - C++
Ребят, помогите с кодом программы: Представить в виде двунаправленного списка схему автобусного маршрута: названия остановок и время...

Определить, какая цифра расположена в числе левее: максимальная или минимальная - C++
Помогите решить задач из задачника Златопольского. дано натуральное число, в котором все цифры различны. определить, какая цифра...


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

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

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