Dada una array*n donde todos los números son distintos, encuentre la ruta de longitud máxima (comenzando desde cualquier celda) tal que todas las celdas a lo largo de la ruta estén en orden creciente con una diferencia de 1.
Podemos movernos en 4 direcciones desde una celda dada ( i, j), es decir, podemos movernos a (i+1, j) o (i, j+1) o (i-1, j) o (i, j-1) con la condición de que las celdas adyacentes tengan una diferencia de 1.
Ejemplo:
Input: mat[][] = {{1, 2, 9}
{5, 3, 8}
{4, 6, 7}}
Output: 4
The longest path is 6-7-8-9.
La idea es simple, calculamos el camino más largo comenzando con cada celda. Una vez que hemos calculado el más largo para todas las celdas, devolvemos el máximo de todos los caminos más largos. Una observación importante en este enfoque son muchos subproblemas superpuestos. Por lo tanto, este problema se puede resolver de manera óptima utilizando Programación Dinámica.
A continuación se muestra una implementación basada en la programación dinámica que utiliza una tabla de búsqueda dp[][] para verificar si un problema ya está resuelto o no.
C++
// C++ program to find the longest path in a matrix
// with given constraints
#include <bits/stdc++.h>
#define n 3
using namespace std;
// Returns length of the longest path beginning with
// mat[i][j]. This function mainly uses lookup table
// dp[n][n]
int findLongestFromACell(int i, int j, int mat[n][n],
int dp[n][n])
{
if (i < 0 || i >= n || j < 0 || j >= n)
return 0;
// If this subproblem is already solved
if (dp[i][j] != -1)
return dp[i][j];
// To store the path lengths in all the four directions
int x = INT_MIN, y = INT_MIN, z = INT_MIN, w = INT_MIN;
// Since all numbers are unique and in range from 1 to
// n*n, there is atmost one possible direction from any
// cell
if (j < n - 1 && ((mat[i][j] + 1) == mat[i][j + 1]))
x = 1 + findLongestFromACell(i, j + 1, mat, dp);
if (j > 0 && (mat[i][j] + 1 == mat[i][j - 1]))
y = 1 + findLongestFromACell(i, j - 1, mat, dp);
if (i > 0 && (mat[i][j] + 1 == mat[i - 1][j]))
z = 1 + findLongestFromACell(i - 1, j, mat, dp);
if (i < n - 1 && (mat[i][j] + 1 == mat[i + 1][j]))
w = 1 + findLongestFromACell(i + 1, j, mat, dp);
// If none of the adjacent fours is one greater we will
// take 1 otherwise we will pick maximum from all the
// four directions
return dp[i][j] = max({x, y, z, w, 1});
}
// Returns length of the longest path beginning with any
// cell
int finLongestOverAll(int mat[n][n])
{
int result = 1; // Initialize result
// Create a lookup table and fill all entries in it as
// -1
int dp[n][n];
memset(dp, -1, sizeof dp);
// Compute longest path beginning from all cells
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dp[i][j] == -1)
findLongestFromACell(i, j, mat, dp);
// Update result if needed
result = max(result, dp[i][j]);
}
}
return result;
}
// Driver program
int main()
{
int mat[n][n]
= { { 1, 2, 9 }, { 5, 3, 8 }, { 4, 6, 7 } };
cout << "Length of the longest path is "
<< finLongestOverAll(mat);
return 0;
}
Java
// Java program to find the longest path in a matrix
// with given constraints
class GFG {
public static int n = 3;
// Function that returns length of the longest path
// beginning with mat[i][j]
// This function mainly uses lookup table dp[n][n]
static int findLongestFromACell(int i, int j,
int mat[][], int dp[][])
{
// Base case
if (i < 0 || i >= n || j < 0 || j >= n)
return 0;
// If this subproblem is already solved
if (dp[i][j] != -1)
return dp[i][j];
// To store the path lengths in all the four
// directions
int x = Integer.MIN_VALUE, y = Integer.MIN_VALUE,
z = Integer.MIN_VALUE, w = Integer.MIN_VALUE;
// Since all numbers are unique and in range from 1
// to n*n, there is atmost one possible direction
// from any cell
if (j < n - 1 && ((mat[i][j] + 1) == mat[i][j + 1]))
x = dp[i][j]
= 1
+ findLongestFromACell(i, j + 1, mat, dp);
if (j > 0 && (mat[i][j] + 1 == mat[i][j - 1]))
y = dp[i][j]
= 1
+ findLongestFromACell(i, j - 1, mat, dp);
if (i > 0 && (mat[i][j] + 1 == mat[i - 1][j]))
z = dp[i][j]
= 1
+ findLongestFromACell(i - 1, j, mat, dp);
if (i < n - 1 && (mat[i][j] + 1 == mat[i + 1][j]))
w = dp[i][j]
= 1
+ findLongestFromACell(i + 1, j, mat, dp);
// If none of the adjacent fours is one greater we
// will take 1 otherwise we will pick maximum from
// all the four directions
return dp[i][j]
= Math.max(
x,
Math.max(y, Math.max(z, Math.max(w, 1))));
}
// Function that returns length of the longest path
// beginning with any cell
static int finLongestOverAll(int mat[][])
{
// Initialize result
int result = 1;
// Create a lookup table and fill all entries in it
// as -1
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
dp[i][j] = -1;
// Compute longest path beginning from all cells
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dp[i][j] == -1)
findLongestFromACell(i, j, mat, dp);
// Update result if needed
result = Math.max(result, dp[i][j]);
}
}
return result;
}
// driver program
public static void main(String[] args)
{
int mat[][]
= { { 1, 2, 9 }, { 5, 3, 8 }, { 4, 6, 7 } };
System.out.println("Length of the longest path is "
+ finLongestOverAll(mat));
}
}
// Contributed by Pramod Kumar
Python3
# Python3 program to find the longest path in a matrix
# with given constraints
n = 3
# Returns length of the longest path beginning with mat[i][j].
# This function mainly uses lookup table dp[n][n]
def findLongestFromACell(i, j, mat, dp):
# Base case
if (i < 0 or i >= n or j < 0 or j >= n):
return 0
# If this subproblem is already solved
if (dp[i][j] != -1):
return dp[i][j]
# To store the path lengths in all the four directions
x, y, z, w = -1, -1, -1, -1
# Since all numbers are unique and in range from 1 to n * n,
# there is atmost one possible direction from any cell
if (j < n-1 and ((mat[i][j] + 1) == mat[i][j + 1])):
x = 1 + findLongestFromACell(i, j + 1, mat, dp)
if (j > 0 and (mat[i][j] + 1 == mat[i][j-1])):
y = 1 + findLongestFromACell(i, j-1, mat, dp)
if (i > 0 and (mat[i][j] + 1 == mat[i-1][j])):
z = 1 + findLongestFromACell(i-1, j, mat, dp)
if (i < n-1 and (mat[i][j] + 1 == mat[i + 1][j])):
w = 1 + findLongestFromACell(i + 1, j, mat, dp)
# If none of the adjacent fours is one greater we will take 1
# otherwise we will pick maximum from all the four directions
dp[i][j] = max(x, max(y, max(z, max(w, 1))))
return dp[i][j]
# Returns length of the longest path beginning with any cell
def finLongestOverAll(mat):
result = 1 # Initialize result
# Create a lookup table and fill all entries in it as -1
dp = [[-1 for i in range(n)]for i in range(n)]
# Compute longest path beginning from all cells
for i in range(n):
for j in range(n):
if (dp[i][j] == -1):
findLongestFromACell(i, j, mat, dp)
# Update result if needed
result = max(result, dp[i][j])
return result
# Driver program
mat = [[1, 2, 9],
[5, 3, 8],
[4, 6, 7]]
print("Length of the longest path is ", finLongestOverAll(mat))
# this code is improved by sahilshelangia
Javascript
<script>
// JavaScript program to find the longest path in a matrix
// with given constraints
let n = 3;
// Returns length of the longest path beginning with mat[i][j].
// This function mainly uses lookup table dp[n][n]
function findLongestFromACell( i, j, mat, dp){
if (i < 0 || i >= n || j < 0 || j >= n)
return 0;
// If this subproblem is already solved
if (dp[i][j] != -1)
return dp[i][j];
// To store the path lengths in all the four directions
let x,y,z,w;
x = -1;
y = -1;
z = -1
w = -1;
// Since all numbers are unique and in range from 1 to n*n,
// there is atmost one possible direction from any cell
if (j < n - 1 && ((mat[i][j] + 1) == mat[i][j + 1]))
x = 1 + findLongestFromACell(i, j + 1, mat, dp);
if (j > 0 && (mat[i][j] + 1 == mat[i][j - 1]))
y = 1 + findLongestFromACell(i, j - 1, mat, dp);
if (i > 0 && (mat[i][j] + 1 == mat[i - 1][j]))
z = 1 + findLongestFromACell(i - 1, j, mat, dp);
if (i < n - 1 && (mat[i][j] + 1 == mat[i + 1][j]))
w = 1 + findLongestFromACell(i + 1, j, mat, dp);
// If none of the adjacent fours is one greater we will take 1
// otherwise we will pick maximum from all the four directions
dp[i][j] = Math.max(x, Math.max(y, Math.max(z, Math.max(w, 1))));
return dp[i][j];
}
// Returns length of the longest path beginning with any cell
function finLongestOverAll( mat){
let result = 1; // Initialize result
// Create a lookup table and fill all entries in it as -1
var dp = [];
for( var y = 0; y < n; y++ ) {
dp[ y ] = [];
for( var x = 0; x < n; x++ ) {
dp[ y ][ x ] = -1;
}
}
// Compute longest path beginning from all cells
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (dp[i][j] == -1)
findLongestFromACell(i, j, mat, dp);
// Update result if needed
result = Math.max(result, dp[i][j]);
}
}
return result;
}
// Driver program
let mat = [[ 1, 2, 9 ],
[ 5, 3, 8 ],
[ 4, 6, 7 ]];
document.write("Length of the longest path is ");
document.write( finLongestOverAll(mat));
</script>
C#
// C# program to find the longest path
// in a matrix with given constraints
using System;
class GFG {
public static int n = 3;
// Function that returns length of
// the longest path beginning with mat[i][j]
// This function mainly uses lookup
// table dp[n][n]
public static int findLongestFromACell(int i, int j,
int[][] mat,
int[][] dp)
{
// Base case
if (i < 0 || i >= n || j < 0 || j >= n) {
return 0;
}
// If this subproblem is
// already solved
if (dp[i][j] != -1) {
return dp[i][j];
}
// To store the path lengths in all the four
// directions
int x = int.MinValue, y = int.MinValue,
z = int.MinValue, w = int.MinValue;
// Since all numbers are unique and
// in range from 1 to n*n, there is
// atmost one possible direction
// from any cell
if (j < n - 1
&& ((mat[i][j] + 1) == mat[i][j + 1])) {
x = dp[i][j]
= 1
+ findLongestFromACell(i, j + 1, mat, dp);
}
if (j > 0 && (mat[i][j] + 1 == mat[i][j - 1])) {
y = dp[i][j]
= 1
+ findLongestFromACell(i, j - 1, mat, dp);
}
if (i > 0 && (mat[i][j] + 1 == mat[i - 1][j])) {
z = dp[i][j]
= 1
+ findLongestFromACell(i - 1, j, mat, dp);
}
if (i < n - 1 && (mat[i][j] + 1 == mat[i + 1][j])) {
w = dp[i][j]
= 1
+ findLongestFromACell(i + 1, j, mat, dp);
}
// If none of the adjacent fours is one greater we
// will take 1 otherwise we will pick maximum from
// all the four directions
dp[i][j] = Math.Max(
x, Math.Max(y, Math.Max(z, Math.Max(w, 1))));
return dp[i][j];
}
// Function that returns length of the
// longest path beginning with any cell
public static int finLongestOverAll(int[][] mat)
{
// Initialize result
int result = 1;
// Create a lookup table and fill
// all entries in it as -1
int[][] dp
= RectangularArrays.ReturnRectangularIntArray(
n, n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = -1;
}
}
// Compute longest path beginning
// from all cells
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dp[i][j] == -1) {
findLongestFromACell(i, j, mat, dp);
}
// Update result if needed
result = Math.Max(result, dp[i][j]);
}
}
return result;
}
public static class RectangularArrays {
public static int[][] ReturnRectangularIntArray(
int size1, int size2)
{
int[][] newArray = new int[size1][];
for (int array1 = 0; array1 < size1; array1++) {
newArray[array1] = new int[size2];
}
return newArray;
}
}
// Driver Code
public static void Main(string[] args)
{
int[][] mat = new int[][] { new int[] { 1, 2, 9 },
new int[] { 5, 3, 8 },
new int[] { 4, 6, 7 } };
Console.WriteLine("Length of the longest path is "
+ finLongestOverAll(mat));
}
}
// This code is contributed by Shrikant13
Producción
Length of the longest path is 4
La complejidad temporal de la solución anterior es O(n 2 ). Puede parecer más a primera vista. Si observamos más de cerca, podemos notar que todos los valores de dp[i][j] se calculan solo una vez.
Espacio Auxiliar: O(N x N),
Este artículo es una contribución de Aarti_Rathi y Ekta Goel . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA