Minimice el costo de viajar desde el origen hasta el destino en una array según el cambio de fila y el costo de cambio de columna dados

Dada una cuadrícula M*N y dada una array startPos[] , que indica que la posición inicial es la celda (startPos[0] , startPos[1]) y la array homePos[] que indica que su destino está en la celda (homePos[ 0], posición de inicio[1]).

Desde cualquier celda, el movimiento solo está permitido en cuatro direcciones: izquierda, derecha, arriba y abajo, y no puede salir del límite. Se dan dos arrays de enteros indexados a 0 : rowCosts[] de longitud M y colCosts[] de longitud N que denota los costes de los movimientos.

Si hay un movimiento hacia arriba o hacia abajo en una celda con la fila r , el costo del movimiento es rowCosts[r] . De manera similar, si se realiza un movimiento hacia la izquierda o hacia la derecha en una celda adyacente c , el movimiento cuesta colCosts .

Devuelve el costo total mínimo para viajar desde el origen hasta el destino.

Nota: No hay costo negativo asociado con ningún movimiento.

Ejemplos:

Entrada: M = 3, N = 4, startPos[] = {1, 0}, homePos[] = {2, 3}, rowCosts[] = {5, 4, 3}, colCosts[] = {8, 2 , 6, 7}
Salida: 18
Explicación: Un camino ideal es: 

• Comienza en (1, 0) y desciende a (2, 0). Este movimiento cuesta rowCosts[2] = 3.
• Va directo a (2, 1). Este movimiento cuesta colCosts[1] = 2.
• Va directamente a (2, 2). Este movimiento cuesta colCosts[2] = 6.
• Va directo a (2, 3). Este movimiento cuesta colCosts[3] = 7.
• El costo total es 3 + 2 + 6 + 7 = 18.

El movimiento se muestra en la siguiente imagen:

Entrada: M = 3, N = 4, startPos[] = {0, 0}, homePos[] = {0, 0}, rowCosts[] = {5, 4, 3}, colCosts[] = {8, 2 , 6, 7}
Salida: 0
Explicación: La posición de inicio y el destino son iguales. Así que no hay coste de movimiento.

Enfoque: La solución se basa en la observación:

Para llegar al destino con un costo mínimo, solo se deben cruzar  las filas que se encuentran en el rango [startPos[0], homePos[0]] y las columnas que se encuentran en el rango [startPos[1], homePos[1]] .
Motivo: cruzar cualquier otra fila o columna agregará un costo adicional ya que todos los movimientos tienen un costo positivo y la cantidad de movimientos aumenta con el cruce adicional de filas y columnas.

 Por lo tanto, el costo de cada fila y columna entre las posiciones de inicio y de inicio se incurrirá exactamente una vez. Calcule el costo de moverse entre las filas homePos[0] y startPos[0] . y las columnas homePos[1] y startPos[1] . Siga los pasos a continuación para resolver el problema:

• Inicialice las variables rmin, cmin como el mínimo de la posición inicial y final.
• Inicialice las variables rmax, cmax como el máximo de la posición inicial y final.
• Itere sobre el rango [rmin, rmax] usando la variable i y realice las siguientes tareas:
  • Agregue el valor rowCosts[i] a la variable ans.
• Itere sobre el rango [cmin, cmax] usando la variable i y realice las siguientes tareas:
  • Agregue el valor colCosts[i] a la variable ans.
• Reste los valores rowCosts[startPos[0]], colCosts[startPos[1]] de la variable ans.
• Después de realizar los pasos anteriores, imprima el valor de ans como respuesta.

A continuación se muestra la implementación del enfoque anterior.

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum cost
int minPathCost(vector<int>& startPos,
                vector<int>& homePos,
                vector<int>& rowCosts,
                vector<int>& colCosts)
{
    int ans = 0;
    int rmin = min(startPos[0], homePos[0]);
    int rmax = max(startPos[0], homePos[0]);
    int cmin = min(startPos[1], homePos[1]);
    int cmax = max(startPos[1], homePos[1]);
 
    // Determine the cost of the rows
    // that cross the path.
    for (int i = rmin; i <= rmax; i++)
        ans += rowCosts[i];
 
    // Determine the cost of the cols
    // that cross the path.
    for (int i = cmin; i <= cmax; i++)
        ans += colCosts[i];
 
    // Starting coordinates need to be
    // excluded from the final result
    ans -= rowCosts[startPos[0]];
    ans -= colCosts[startPos[1]];
 
    return ans;
}
 
// Driver Code
int main()
{
    vector<int> startpos{ 1, 0 };
    vector<int> homepos{ 2, 3 };
    vector<int> roscost{ 5, 4, 3 };
    vector<int> colcst{ 8, 2, 6, 7 };
 
    cout << minPathCost(startpos, homepos,
                        roscost, colcst);
 
    return 0;
}

// Java code to implement the above approach
import java.util.*;
public class GFG
{
   
  // Function to find the minimum cost
  static int minPathCost(int []startPos,
                         int []homePos,
                         int []rowCosts,
                         int []colCosts)
  {
    int ans = 0;
    int rmin = Math.min(startPos[0], homePos[0]);
    int rmax = Math.max(startPos[0], homePos[0]);
    int cmin = Math.min(startPos[1], homePos[1]);
    int cmax = Math.max(startPos[1], homePos[1]);
 
    // Determine the cost of the rows
    // that cross the path.
    for (int i = rmin; i <= rmax; i++)
      ans += rowCosts[i];
 
    // Determine the cost of the cols
    // that cross the path.
    for (int i = cmin; i <= cmax; i++)
      ans += colCosts[i];
 
    // Starting coordinates need to be
    // excluded from the final result
    ans -= rowCosts[startPos[0]];
    ans -= colCosts[startPos[1]];
 
    return ans;
  }
 
  // Driver code
  public static void main(String args[])
  {
    int []startpos = { 1, 0 };
    int []homepos = { 2, 3 };
    int []roscost = { 5, 4, 3 };
    int []colcst = { 8, 2, 6, 7 };
    System.out.println( minPathCost(startpos, homepos,
                                    roscost, colcst));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

# Python code to implement the above approach
 
# Function to find the minimum cost
def minPathCost(startPos, homePos, rowCosts, colCosts):
    ans = 0;
    rmin = min(startPos[0], homePos[0]);
    rmax = max(startPos[0], homePos[0]);
    cmin = min(startPos[1], homePos[1]);
    cmax = max(startPos[1], homePos[1]);
 
    # Determine the cost of the rows
    # that cross the path.
    for i in range(rmin,rmax+1):
        ans += rowCosts[i];
 
    # Determine the cost of the cols
    # that cross the path.
    for i in range(cmin, cmax + 1):
        ans += colCosts[i];
 
    # Starting coordinates need to be
    # excluded from the final result
    ans -= rowCosts[startPos[0]];
    ans -= colCosts[startPos[1]];
 
    return ans;
 
# Driver code
if __name__ == '__main__':
    startpos = [1, 0];
    homepos = [2, 3];
    roscost = [5, 4, 3];
    colcst = [8, 2, 6, 7];
    print(minPathCost(startpos, homepos, roscost, colcst));
 
# This code is contributed by 29AjayKumar

// C# code to implement the above approach
using System;
 
public class GFG
{
   
  // Function to find the minimum cost
  static int minPathCost(int []startPos,
                         int []homePos,
                         int []rowCosts,
                         int []colCosts)
  {
    int ans = 0;
    int rmin = Math.Min(startPos[0], homePos[0]);
    int rmax = Math.Max(startPos[0], homePos[0]);
    int cmin = Math.Min(startPos[1], homePos[1]);
    int cmax = Math.Max(startPos[1], homePos[1]);
 
    // Determine the cost of the rows
    // that cross the path.
    for (int i = rmin; i <= rmax; i++)
      ans += rowCosts[i];
 
    // Determine the cost of the cols
    // that cross the path.
    for (int i = cmin; i <= cmax; i++)
      ans += colCosts[i];
 
    // Starting coordinates need to be
    // excluded from the readonly result
    ans -= rowCosts[startPos[0]];
    ans -= colCosts[startPos[1]];
 
    return ans;
  }
 
  // Driver code
  public static void Main(String []args)
  {
    int []startpos = { 1, 0 };
    int []homepos = { 2, 3 };
    int []roscost = { 5, 4, 3 };
    int []colcst = { 8, 2, 6, 7 };
    Console.WriteLine( minPathCost(startpos, homepos,
                                    roscost, colcst));
  }
}
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript program for the above approach
 
// Function to find the minimum cost
function minPathCost(startPos, homePos,
                     rowCosts, colCosts)
{
    let ans = 0;
    let rmin = Math.min(startPos[0], homePos[0]);
    let rmax = Math.max(startPos[0], homePos[0]);
    let cmin = Math.min(startPos[1], homePos[1]);
    let cmax = Math.max(startPos[1], homePos[1]);
 
    // Determine the cost of the rows
    // that cross the path.
    for(let i = rmin; i <= rmax; i++)
        ans += rowCosts[i];
 
    // Determine the cost of the cols
    // that cross the path.
    for(let i = cmin; i <= cmax; i++)
        ans += colCosts[i];
 
    // Starting coordinates need to be
    // excluded from the final result
    ans -= rowCosts[startPos[0]];
    ans -= colCosts[startPos[1]];
 
    return ans;
}
 
// Driver Code
let startpos = [ 1, 0 ];
let homepos = [ 2, 3 ];
let roscost = [ 5, 4, 3 ];
let colcst = [ 8, 2, 6, 7 ];
 
document.write(minPathCost(startpos, homepos,
                           roscost, colcst));
 
// This code is contributed by Potta Lokesh
 
</script>

18

Complejidad temporal: O(M + N)
Espacio auxiliar: O(1)