Минимизация затрат на перемещение от источника к месту назначения в матрице на основе данной стоимости изменения строки и столбца.

Опубликовано: 20 Сентября, 2022

Учитывая сетку M*N и заданный массив startPos[] , указывающий, что начальная позиция является ячейкой (startPos[0] , startPos[1]) , и массив homePos[] , указывающий, что его пункт назначения находится в ячейке (homePos[ 0], homePos[1]).

Из любой ячейки движение разрешено только в четырех направлениях: влево, вправо, вверх и вниз, и не может выходить за границу. Даны два целочисленных массива с нулевым индексом : rowCosts[] длины M и colCosts[] длины N , которые обозначают стоимость перемещений.

Если есть движение вверх или вниз в ячейку со строкой r , стоимость перемещения равна rowCosts[r] . Точно так же, если движение осуществляется влево или вправо в соседнюю ячейку c , перемещение стоит colCosts .

Возвращает минимальную общую стоимость поездки из источника в пункт назначения.

Примечание. Никакая отрицательная стоимость не связана с любым перемещением.

Примеры:

Input: M = 3, N = 4, startPos[] = {1, 0}, homePos[] = {2, 3}, rowCosts[] = {5, 4, 3}, colCosts[] = {8, 2, 6, 7}
Output: 18
Explanation: One ideal path is: 

  • It starts at (1, 0) and descends to (2, 0). This move costs rowCosts[2] = 3.
  • It goes straight to (2, 1). This move costs colCosts[1] = 2.
  • It goes straight to (2, 2). This move costs colCosts[2] = 6.
  • It goes straight to (2, 3). This move costs colCosts[3] = 7.
  • The total cost is 3 + 2 + 6 + 7 = 18.

The movement is shown in the picture below:

Input: M = 3, N = 4, startPos[] = {0, 0}, homePos[] = {0, 0}, rowCosts[] = {5, 4, 3}, colCosts[] = {8, 2, 6, 7}
Output: 0
Explanation: Starting position and destination both are same. So no movement cost.

Подход: Решение основано на наблюдении:

To reach destination with minimum cost only the rows lying in the range [startPos[0], homePos[0]] and columns lying in the range [startPos[1], homePos[1]] should be crossed. 
Reason: Crossing any other row or column will add extra cost as all the movements have positive cost and number of movements increases with extra row and column traversal.

Таким образом, стоимость каждой строки и столбца между исходной и начальной позициями будет понесена ровно один раз. Рассчитать стоимость перемещения между строками homePos[0] и startPos[0] . и столбцы homePos[1] и startPos[1] . Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте переменные rmin, cmin как минимум начальной и конечной позиции.
  • Инициализируйте переменные rmax, cmax как максимум начальной и конечной позиции.
  • Переберите диапазон [rmin, rmax], используя переменную i , и выполните следующие задачи:
    • Добавьте значение rowCosts[i] в переменную ans.
  • Переберите диапазон [cmin, cmax], используя переменную i , и выполните следующие задачи:
    • Добавьте значение colCosts[i] к переменной ans.
  • Вычтите значения rowCosts[startPos[0]], colCosts[startPos[1]] из переменной ans.
  • После выполнения вышеуказанных шагов выведите значение ans в качестве ответа.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(M + N)
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ