Rover. Finding the shortest path by Dijkstra’s shortest path algorithm

Вы — инженер, проектирующий роверы-беспилотники. Вам надо спроектировать путь ровера по заранее известной местности с максимальной экономией заряда.

Вам пришли данные о местности в закодированном виде: фотография, сконвертированная в матрицу с числами. Одна матрица — это прямоугольный снимок размером х на y метров. Вот пример одной такой сконвертированной фотографии, на ней снимок в 100 на 100 метров:

Фото 1: 
0 2 3 4 1
2 3 4 4 1
3 4 5 6 2
4 5 6 7 1
6 7 8 7 1

Числа показывают высоту над уровнем моря. 0 — это высота ровно на уровне моря, а, например, 4 — это 4 единицы над уровнем моря. На Фото 1 закодирован холм, пологий слева и резко обрывающийся справа. Небольшой холмик выглядел бы вот так

Фото 2: 
0 1 1 1 0
1 1 3 1 1
0 1 1 1 0
0 0 0 0 0

А вот так: ложбина между двумя холмами

Фото 3: 
1 1 2 3 4
1 0 1 2 3
2 1 1 1 2
3 3 1 0 1
4 3 1 1 0

На этих данных - скала или овраг, так как виден очень резкий перепад высот в середине снимка

Фото 4: 
1 1 6 7 7
1 1 6 7 8
1 6 7 8 9

А на этом - маленькая ямка

Фото 5: 
3 4 4 4 4 3
3 2 1 1 1 4
4 2 1 1 3 4
4 4 2 2 3 4

Данные придут вам в виде матрицы с неотрицательными числами. Размер матрицы NxM.

Ровер всегда движется из верхней левой точки [0][0] в правую нижнюю точку [N - 1][M - 1], где N и M - это длина и ширина матрицы. Это надо для того, чтобы разрезать фотографию на одинаковые куски, обработать их по-отдельности, а потом склеить весь путь. У вашего ровера есть несколько ограничений:

Из любой точки ровер может двигаться только в четыре стороны: на север, юг, запад, восток. Ровер не может ехать по-диагонали — эта функция еще не реализована. Ровер не может вернуться в ту точку, в которой уже был.

Ровер ездит на заряде. Вы знаете, что для ровера очень затратно подниматься и опускаться. Он тратит единицу заряда на само движение, и дополнительные единицы на подъем и спуск. Ровер бы вообще спокойно жил, если бы ездил по асфальту в Беларуси, тогда бы он тратил себе линейно заряд и в ус не дул, но жизнь его сложилась иначе.

Заряд расходуется по правилу: На 1 шаг ровер всегда тратит 1 единицу заряда. На подъем или спуск ровер тратит заряд, пропорциональный сложности подъема или спуска. Сложность подъема или спуска - это разница между высотами.

Например, в такой местности

1 2
1 5

на путь из [0][0] в [0][1] ровер потратит 2 единицы заряд: 1 единица заряда на само движение, и еще 1 единицу заряда на подъем в [0][1]. А из [0][1] в [1][1] ровер потратит 4 единицы заряда: 1 единица на само движение, и 3 единицы (5 - 2) на подъем Вам надо рассчитать путь ровера из верхей левой [0][0] точки в правую нижнюю [N - 1][M - 1] точку с минимальной тратой заряда. Вы не заранее знаете размер фотографии, которую будете обрабатывать, N и M - произвольные неотрицательные числа.

Сделайте план пути и планируемый расход и выведите. Для фотографии

0 4
1 3

план будет такой:

[0][0]->[1][0]->[1][1]
steps: 2
fuel: 5

Ровер едет из 0 в 1 в 3, сделает два шага, потратит 5 заряда. Если бы он поехал сначала в 4, потом в 3, он бы сделал то же количество шагов, но потратил бы 7 заряда. Оптимальный путь: 2 шага и 5 заряда. Если на карте есть несколько вариантов пути, выберите любой из них.