Número total de caminos decrecientes en una array

Dada una array de tamaño NXN de enteros. La tarea es encontrar el número de caminos decrecientes en la array. Puede comenzar desde cualquier celda y desde la celda (i, j), puede moverse a (i + 1, j), (i – 1, j), (i, j + 1) y (i , j – 1) celda.
Ejemplos: 
 

Input : m[][] = { { 1, 2 }, 
                  { 1, 3 } }
Output : 8
Explanation : Decreasing paths are { 1 }, { 1 }, { 2 }, { 3 },
              { 2, 1 }, { 3, 1 }, { 3, 2 }, { 3, 2, 1 }

Input : m[][] = { { 1, 2, 3 },
                  { 1, 3, 4 },
                  { 1, 5, 6 } }
Output : 41

La idea para solucionar este problema es utilizar Programación Dinámica. Declare una array dp[][] , donde dp[i][j] almacena el número de rutas decrecientes que se pueden formar a partir de la celda (i, j) . Entonces, definiremos una función recursiva para evaluar el número de caminos decrecientes con parámetros, digamos i, j, el número de fila y el número de columna de la celda actual. Realice todos los movimientos posibles desde la celda (i,j) y lleve la cuenta del número total de caminos. Primero, verificaremos en la función que el número de caminos decrecientes para la posición de entrada (i, j) ya está calculado o no. En caso afirmativo, devuelva el valor dp[i][j]de lo contrario, encuentre el número de secuencias decrecientes permitidas en cuatro direcciones y devuelva el valor. Mientras tanto, también almacenaremos el número de decrecientes para las celdas intermedias. Dado que DP[i][j] almacena el número de caminos decrecientes para cada celda, la suma de todas las celdas de DP[][] responderá al conteo de caminos decrecientes en la array completa. 
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// CPP program to count number
// of decreasing path in a matrix
#include <bits/stdc++.h>
using namespace std;
#define MAX 100
 
// Function that returns the number of
// decreasing paths from a cell(i, j)
int CountDecreasingPathsCell(int mat[MAX][MAX], int dp[MAX][MAX],
                                              int n, int x, int y)
{
    // checking if already calculated
    if (dp[x][y] != -1)
        return dp[x][y];
 
    // all possible paths
    int delta[4][2] = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } };
    int newx, newy;
 
    // counts the total number of paths
    int ans = 1;
 
    // In all four allowed direction.
    for (int i = 0; i < 4; i++) {
 
        // new co-ordinates
        newx = x + delta[i][0];
        newy = y + delta[i][1];
 
        // Checking if not going out of matrix and next
        // cell value is less than current cell value.
        if (newx >= 0 && newx < n && newy >= 0
            && newy < n && mat[newx][newy] < mat[x][y]) {
            ans += CountDecreasingPathsCell(mat, dp, n, newx, newy);
        }
    }
    // function that returns the answer
    return dp[x][y] = ans;
}
 
// Function that counts the total
// decreasing path in the matrix
int countDecreasingPathsMatrix(int n,
                               int mat[MAX][MAX])
{
    int dp[MAX][MAX];
 
    // Initialising dp[][] to -1.
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dp[i][j] = -1;
 
    int sum = 0;
 
    // Calculating number of decreasing path from each cell.
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            sum += CountDecreasingPathsCell(mat, dp, n, i, j);
 
    return sum;
}
 
// Driver Code
int main()
{
    int n = 2;
 
    int mat[MAX][MAX] = { { 1, 2 }, { 1, 3 } };
    // function call that returns the
    // count of decreasing paths in a matrix
    cout << countDecreasingPathsMatrix(n, mat)
         << endl;
    return 0;
}

Python3

# Python3 program to count number
# of decreasing path in a matrix
MAX = 100
 
# Function that returns the number of
# decreasing paths from a cell(i, j)
def CountDecreasingPathsCell(mat, dp, n, x, y):
     
    # checking if already calculated
    if (dp[x][y] != -1):
        return dp[x][y]
         
    # all possible paths
    delta = [[0, 1], [1, 0],
             [-1, 0], [0, -1]]
    newx, newy = 0, 0
     
    # counts the total number of paths
    ans = 1
     
    # In all four allowed direction.
    for i in range(4):
         
        # new co-ordinates
        newx = x + delta[i][0]
        newy = y + delta[i][1]
         
        # Checking if not going out of matrix and next
        # cell value is less than current cell value.
        if (newx >= 0 and newx < n and newy >= 0 and
            newy < n and mat[newx][newy] < mat[x][y]):
            ans += CountDecreasingPathsCell(mat, dp, n,
                                            newx, newy)
                                             
    # function that returns the answer
    dp[x][y] = ans
    return dp[x][y]
 
# Function that counts the total
# decreasing path in the matrix
def countDecreasingPathsMatrix(n,mat):
    dp = []
     
    # Initialising dp[][] to -1.
    for i in range(n):
        l = []
        for j in range(n):
            l.append(-1)
        dp.append(l)
    sum = 0
     
    # Calculating number of decreasing
    # path from each cell.
    for i in range(n):
        for j in range(n):
            sum += CountDecreasingPathsCell(mat, dp,
                                            n, i, j)
    return sum
     
# Driver Code
n = 2
mat = [[1, 2], [1, 3]]
 
# function call that returns the
# count of decreasing paths in a matrix
print(countDecreasingPathsMatrix(n, mat))
 
# This code is contributed by SHUBHAMSINGH10

C#

// C# program to count number
// of decreasing path in a matrix
using System;
 
class GFG
{
     
// Function that returns
// the number of decreasing
// paths from a cell(i, j)
public static int CountDecreasingPathsCell(int[,] mat, int[,] dp,
                                           int n, int x, int y)
{
    // checking if already
    // calculated
    if (dp[x, y] != -1)
        return dp[x, y];
 
    // all possible paths
    int[,] delta = {{0, 1}, {1, 0},
                    {-1, 0},{0, -1}};
    int newx, newy;
 
    // counts the total
    // number of paths
    int ans = 1;
 
    // In all four
    // allowed direction.
    for (int i = 0; i < 4; i++)
    {
 
        // new co-ordinates
        newx = x + delta[i,0];
        newy = y + delta[i,1];
 
        // Checking if not going out
        // of matrix and next cell
        // value is less than current
        // cell value.
        if (newx >= 0 && newx < n &&
            newy >= 0 && newy < n &&
            mat[newx,newy] < mat[x,y])
        {
            ans += CountDecreasingPathsCell(mat, dp, n,
                                            newx, newy);
        }
    }
     
    // function that
    // returns the answer
    return dp[x,y] = ans;
}
 
// Function that counts the total
// decreasing path in the matrix
public static int countDecreasingPathsMatrix(int n,
                                        int[,] mat)
{
    int[,] dp = new int[n, n];
 
    // Initialising dp[][] to -1.
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dp[i, j] = -1;
 
    int sum = 0;
 
    // Calculating number of
    // decreasing path from each cell.
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            sum += CountDecreasingPathsCell(mat, dp,
                                            n, i, j);
 
    return sum;
}
 
// Driver code
static public void Main ()
{
    int n = 2;
     
    int[,] mat= {{1, 2},
                {1, 3}};
     
    // function call that returns the
    // count of decreasing paths in a matrix
    Console.WriteLine(countDecreasingPathsMatrix(n, mat));
}
}
 
// This code is contributed by vij.

Javascript

<script>
 
// Javascript program to count number
// of decreasing path in a matrix
var MAX = 100
 
// Function that returns the number of
// decreasing paths from a cell(i, j)
function CountDecreasingPathsCell(mat, dp, n, x, y)
{
    // checking if already calculated
    if (dp[x][y] != -1)
        return dp[x][y];
 
    // all possible paths
    var delta = [ [ 0, 1 ], [ 1, 0 ], [ -1, 0 ],
    [ 0, -1 ] ];
    var newx, newy;
 
    // counts the total number of paths
    var ans = 1;
 
    // In all four allowed direction.
    for (var i = 0; i < 4; i++) {
 
        // new co-ordinates
        newx = x + delta[i][0];
        newy = y + delta[i][1];
 
        // Checking if not going out of matrix and next
        // cell value is less than current cell value.
        if (newx >= 0 && newx < n && newy >= 0
            && newy < n && mat[newx][newy] < mat[x][y])
            {
            ans += CountDecreasingPathsCell
            (mat, dp, n, newx, newy);
        }
    }
    // function that returns the answer
    dp[x][y] = ans;
    return ans;
}
 
// Function that counts the total
// decreasing path in the matrix
function countDecreasingPathsMatrix(n, mat)
{
    var dp = Array.from(Array(MAX),
    ()=> Array(MAX));
 
    // Initialising dp[][] to -1.
    for (var i = 0; i < n; i++)
        for (var j = 0; j < n; j++)
            dp[i][j] = -1;
 
    var sum = 0;
 
    // Calculating number of decreasing
    // path from each cell.
    for (var i = 0; i < n; i++)
        for (var j = 0; j < n; j++)
            sum += CountDecreasingPathsCell
            (mat, dp, n, i, j);
 
    return sum;
}
 
// Driver Code
 
var n = 2;
var mat = [ [ 1, 2 ], [ 1, 3 ] ];
 
// function call that returns the
// count of decreasing paths in a matrix
document.write( countDecreasingPathsMatrix(n, mat));
 
 
</script>
Producción: 

8

 

Complejidad de Tiempo : O(N 2
Espacio Auxiliar : O(N 2 )
 

Publicación traducida automáticamente

Artículo escrito por anuj0503 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *