Encuentre los pasos mínimos necesarios para llegar al final de una array | conjunto 2

Dada una array 2d que consta de números enteros positivos, la tarea es encontrar el número mínimo de pasos necesarios para llegar al final de la array. Si estamos en la celda (i, j) entonces podemos ir a todas las celdas representadas por (i + X, j + Y) tal que X ≥ 0 , Y ≥ 0 y X + Y = arr[i][j] . Si no existe una ruta, imprima -1 .
Ejemplos: 
 

Entrada: arr[][] = { 
{4, 1, 1}, 
{1, 1, 1}, 
{1, 1, 1}} 
Salida: 1 
La ruta será desde {0, 0} -> {2 , 2} ya que la distancia de Manhattan 
entre dos es 4. 
Por lo tanto, estamos llegando allí en 1 paso.
Entrada: arr[][] = { 
{1, 1, 2}, 
{1, 1, 1}, 
{2, 1, 1}} 
Salida: 3 
 

Una solución simple será explorar todas las soluciones posibles, lo que llevará un tiempo exponencial.
Una solución eficiente es usar programación dinámica para resolver este problema en tiempo polinomial. Decidamos los estados de dp. 
Digamos que estamos en la celda (i, j) . Intentaremos encontrar el número mínimo de pasos necesarios para llegar a la celda (n – 1, n – 1) desde esta celda. 
Tenemos arr[i][j] + 1 caminos posibles.
La relación de recurrencia será 
 

dp[i][j] = 1 + min(dp[i][j + arr[i][j]], dp[i + 1][j + arr[i][j] – 1], …. , dp[i + arr[i][j]][j]) 
 

Para reducir el número de términos en la relación de recurrencia, podemos poner un límite superior a los valores de X e Y. ¿Cómo? 
Sabemos que i + X < N . Por lo tanto, X < N – i , de lo contrario, se saldrían de los límites. 
Del mismo modo, Y < N – j
 

0 ≤ Y < N – j …(1) 
X + Y = arr[i][j] …(2) 
Sustituyendo el valor de Y del segundo al primero, obtenemos 
X ≥ arr[i][j] + j – N + 1 
 

Desde arriba obtenemos otro límite inferior en la restricción de X , es decir , X ≥ arr[i][j] + j – N + 1 . 
Entonces, el nuevo límite inferior de X se convierte en X ≥ max(0, arr[i][j] + j – N + 1) . 
También X ≤ min(arr[i][j], N – i – 1) .
Nuestra relación de recurrencia se optimiza para 
 

dp[i][j] = 1 + min(dp[i + max(0, array[i][j] + j – N + 1)][j + array[i][j] – max(0, arr[i][j] + j – N + 1)], …., dp[i + min(arr[i][j], N – i – 1)][j + arr[i][j] – min(array[i][j], N – i – 1)]) 
 

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

// C++ implementation of the approach
#include <bits/stdc++.h>
#define n 3
using namespace std;
 
// 2d array to store
// states of dp
int dp[n][n];
 
// Array to determine whether
// a state has been solved before
int v[n][n];
 
// Function to return the minimum steps required
int minSteps(int i, int j, int arr[][n])
{
 
    // Base cases
    if (i == n - 1 and j == n - 1)
        return 0;
 
    if (i > n - 1 || j > n - 1)
        return 9999999;
 
    // If a state has been solved before
    // it won't be evaluated again
    if (v[i][j])
        return dp[i][j];
 
    v[i][j] = 1;
    dp[i][j] = 9999999;
 
    // Recurrence relation
    for (int k = max(0, arr[i][j] + j - n + 1);
         k <= min(n - i - 1, arr[i][j]); k++) {
        dp[i][j] = min(dp[i][j], minSteps(i + k, j + arr[i][j] - k, arr));
    }
 
    dp[i][j]++;
 
    return dp[i][j];
}
 
// Driver code
int main()
{
    int arr[n][n] = { { 4, 1, 2 },
                      { 1, 1, 1 },
                      { 2, 1, 1 } };
 
    int ans = minSteps(0, 0, arr);
    if (ans >= 9999999)
        cout << -1;
    else
        cout << ans;
 
    return 0;
}

// Java implementation of the approach
class GFG {
 
    static int n = 3;
 
    // 2d array to store
    // states of dp
    static int[][] dp = new int[n][n];
 
    // Array to determine whether
    // a state has been solved before
    static int[][] v = new int[n][n];
 
    // Function to return the minimum steps required
    static int minSteps(int i, int j, int arr[][])
    {
 
        // Base cases
        if (i == n - 1 && j == n - 1) {
            return 0;
        }
 
        if (i > n - 1 || j > n - 1) {
            return 9999999;
        }
 
        // If a state has been solved before
        // it won't be evaluated again
        if (v[i][j] == 1) {
            return dp[i][j];
        }
 
        v[i][j] = 1;
        dp[i][j] = 9999999;
 
        // Recurrence relation
        for (int k = Math.max(0, arr[i][j] + j - n + 1);
             k <= Math.min(n - i - 1, arr[i][j]); k++) {
            dp[i][j] = Math.min(dp[i][j],
                                minSteps(i + k, j + arr[i][j] - k, arr));
        }
 
        dp[i][j]++;
 
        return dp[i][j];
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[][] = { { 4, 1, 2 },
                        { 1, 1, 1 },
                        { 2, 1, 1 } };
 
        int ans = minSteps(0, 0, arr);
        if (ans >= 9999999) {
            System.out.println(-1);
        }
        else {
            System.out.println(ans);
        }
    }
}
 
// This code contributed by Rajput-Ji

# Python3 implementation of the approach
 
import numpy as np
n = 3
 
# 2d array to store
# states of dp
dp = np.zeros((n,n))
 
# Array to determine whether
# a state has been solved before
v = np.zeros((n,n));
 
# Function to return the minimum steps required
def minSteps(i, j, arr) :
 
    # Base cases
    if (i == n - 1 and j == n - 1) :
        return 0;
 
    if (i > n - 1 or j > n - 1) :
        return 9999999;
 
    # If a state has been solved before
    # it won't be evaluated again
    if (v[i][j]) :
        return dp[i][j];
 
    v[i][j] = 1;
    dp[i][j] = 9999999;
 
    # Recurrence relation
    for k in range(max(0, arr[i][j] + j - n + 1),min(n - i - 1, arr[i][j]) + 1) :
        dp[i][j] = min(dp[i][j], minSteps(i + k, j + arr[i][j] - k, arr));
     
 
    dp[i][j] += 1;
 
    return dp[i][j];
 
 
# Driver code
if __name__ == "__main__" :
 
    arr = [
            [ 4, 1, 2 ],
            [ 1, 1, 1 ],
            [ 2, 1, 1 ]
            ];
 
    ans = minSteps(0, 0, arr);
    if (ans >= 9999999) :
        print(-1);
    else :
        print(ans);
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG
{
    static int n = 3;
 
    // 2d array to store
    // states of dp
    static int[,] dp = new int[n, n];
 
    // Array to determine whether
    // a state has been solved before
    static int[,] v = new int[n, n];
 
    // Function to return the minimum steps required
    static int minSteps(int i, int j, int [,]arr)
    {
 
        // Base cases
        if (i == n - 1 && j == n - 1)
        {
            return 0;
        }
 
        if (i > n - 1 || j > n - 1)
        {
            return 9999999;
        }
 
        // If a state has been solved before
        // it won't be evaluated again
        if (v[i, j] == 1)
        {
            return dp[i, j];
        }
 
        v[i, j] = 1;
        dp[i, j] = 9999999;
 
        // Recurrence relation
        for (int k = Math.Max(0, arr[i,j] + j - n + 1);
            k <= Math.Min(n - i - 1, arr[i,j]); k++)
        {
            dp[i,j] = Math.Min(dp[i,j],
                                minSteps(i + k, j + arr[i,j] - k, arr));
        }
 
        dp[i,j]++;
 
        return dp[i,j];
    }
 
    // Driver code
    static public void Main ()
    {
        int [,]arr = { { 4, 1, 2 },
                        { 1, 1, 1 },
                        { 2, 1, 1 } };
 
        int ans = minSteps(0, 0, arr);
        if (ans >= 9999999)
        {
            Console.WriteLine(-1);
        }
        else
        {
            Console.WriteLine(ans);
        }
    }
}
 
// This code contributed by ajit.

<script>   
    // Javascript implementation of the approach
     
    let n = 3;
   
    // 2d array to store
    // states of dp
    let dp = new Array(n);
   
    // Array to determine whether
    // a state has been solved before
    let v = new Array(n);
    for(let i = 0; i < n; i++)
    {
        dp[i] = new Array(n);
        v[i] = new Array(n);
        for(let j = 0; j < n; j++)
        {
            dp[i][j] = 0;
            v[i][j] = 0;
        }
    }
   
    // Function to return the minimum steps required
    function minSteps(i, j, arr)
    {
   
        // Base cases
        if (i == n - 1 && j == n - 1) {
            return 0;
        }
   
        if (i > n - 1 || j > n - 1) {
            return 9999999;
        }
   
        // If a state has been solved before
        // it won't be evaluated again
        if (v[i][j] == 1) {
            return dp[i][j];
        }
   
        v[i][j] = 1;
        dp[i][j] = 9999999;
   
        // Recurrence relation
        for (let k = Math.max(0, arr[i][j] + j - n + 1);
             k <= Math.min(n - i - 1, arr[i][j]); k++) {
            dp[i][j] = Math.min(dp[i][j],
                                minSteps(i + k, j + arr[i][j] - k, arr));
        }
   
        dp[i][j]++;
   
        return dp[i][j];
    }
     
    let arr = [ [ 4, 1, 2 ],
               [ 1, 1, 1 ],
               [ 2, 1, 1 ] ];
   
    let ans = minSteps(0, 0, arr);
    if (ans >= 9999999) {
      document.write(-1);
    }
    else {
      document.write(ans);
    }
 
</script>

1

La complejidad temporal del enfoque anterior será O(n ³ ). Cada estado toma tiempo O(n) en el peor de los casos para resolverse.