Dada una array mat[][] y las coordenadas del Node de origen y destino, la tarea es encontrar la longitud del camino más largo desde el origen hasta el destino.
Ejemplo:
Entrada: mat[][] = {{5, 6, 7, 8}, {4, 1, 0, 9}, {3, 2, 11, 10}}, src = {1, 1}, dest = {2, 2}
Salida: 11
Explicación: El camino más largo entre las coordenadas (1, 1) y (2, 2) tiene 11 Nodes y el camino se da como 1 -> 2 -> 3 -> 4 -> 5 – > 6 -> 7 -> 8 -> 9 -> 10 -> 11.Entrada: mat = {{5, 4, 1, 0}, {6, 3, 2, 0}, {7, 8, 9, 0}}, src = {0, 1}, destino = {2, 2 }
Salida: 12
Enfoque: El problema dado se puede resolver usando recursividad y retroceso . La idea es utilizar la búsqueda en profundidad para explorar cada ruta desde el origen hasta el destino y calcular el número de Nodes entre la ruta. Siga los pasos a continuación para resolver el problema:
- Aplique la búsqueda en profundidad desde el Node de origen hasta el Node de destino
- Recorra en las cuatro direcciones mencionadas y en cada Node, incremente el número de Nodes recorridos.
- Marque los Nodes en la ruta actual como visitados en la array visited[][] y llame recursivamente a los Nodes no visitados en las cuatro direcciones.
- Después de llegar al Node de destino, actualice la cantidad máxima de Nodes necesarios para viajar para llegar al destino.
- Mantenga el número máximo de Nodes en todas las rutas, que es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
// Depth-First-Search function for
// recursion and backtracking
void dfs(vector<vector<int>> mat, int maxi[],
vector<vector<int>> visited, int len,
int i, int j, int dest[])
{
// Return if current node is already
// visited or it is out of bounds
if (i < 0 || j < 0 || i == mat.size() || j == mat[0].size() || visited[i][j])
return;
// If reached the destination
// then update maximum length
if (i == dest[0] && j == dest[1])
{
// Update max
maxi[0] = max(maxi[0], len);
return;
}
// Mark current node as visited
visited[i][j] = true;
// Recursive call in all
// the four directions
dfs(mat, maxi, visited, len + 1, i, j - 1, dest);
dfs(mat, maxi, visited, len + 1, i + 1, j, dest);
dfs(mat, maxi, visited, len + 1, i - 1, j, dest);
dfs(mat, maxi, visited, len + 1, i, j + 1, dest);
// Mark current cell as unvisited
visited[i][j] = false;
}
// Function to find the length of
// the longest path between two nodes
int longestPath(vector<vector<int>> mat, int src[],
int dest[])
{
// Initialize a variable to
// calculate longest path
int maxi[1];
maxi[0] = 0;
// Number of rows
int N = mat.size();
// Number of columns
int M = mat[0].size();
// Initialize a boolean matrix to
// keep track of the cells visited
vector<vector<int>> visited(N, vector<int>(M, 0));
// Call the depth-first-search
dfs(mat, maxi, visited, 0, src[0], src[1], dest);
// Return the answer
return maxi[0] + 1;
}
// Driver code
int main()
{
vector<vector<int>> mat = {{5, 6, 7, 8},
{4, 1, 0, 9},
{3, 2, 11, 10}};
int src[] = {1, 1};
int dest[] = {2, 2};
cout << (longestPath(mat, src, dest));
}
// This code is contributed by Potta Lokesh
Java
// Java implementation for the above approach
import java.io.*;
import java.lang.Math;
import java.util.*;
// Driver code
class GFG {
// Function to find the length of
// the longest path between two nodes
public static int longestPath(int[][] mat, int[] src,
int[] dest)
{
// Initialize a variable to
// calculate longest path
int[] max = new int[1];
// Number of rows
int N = mat.length;
// Number of columns
int M = mat[0].length;
// Initialize a boolean matrix to
// keep track of the cells visited
boolean[][] visited = new boolean[N][M];
// Call the depth-first-search
dfs(mat, max, visited, 0, src[0], src[1], dest);
// Return the answer
return max[0] + 1;
}
// Depth-First-Search function for
// recursion and backtracking
public static void dfs(int[][] mat, int[] max,
boolean[][] visited, int len,
int i, int j, int[] dest)
{
// Return if current node is already
// visited or it is out of bounds
if (i < 0 || j < 0 || i == mat.length
|| j == mat[0].length || visited[i][j])
return;
// If reached the destination
// then update maximum length
if (i == dest[0] && j == dest[1]) {
// Update max
max[0] = Math.max(max[0], len);
return;
}
// Mark current node as visited
visited[i][j] = true;
// Recursive call in all
// the four directions
dfs(mat, max, visited, len + 1, i, j - 1, dest);
dfs(mat, max, visited, len + 1, i + 1, j, dest);
dfs(mat, max, visited, len + 1, i - 1, j, dest);
dfs(mat, max, visited, len + 1, i, j + 1, dest);
// Mark current cell as unvisited
visited[i][j] = false;
}
// Driver code
public static void main(String[] args)
{
int[][] mat = { { 5, 6, 7, 8 },
{ 4, 1, 0, 9 },
{ 3, 2, 11, 10 } };
int[] src = { 1, 1 };
int[] dest = { 2, 2 };
System.out.println(longestPath(mat, src, dest));
}
}
Python3
# Python 3 implementation for the above approach # Depth-First-Search function for # recursion and backtracking def dfs(mat, maxi, visited, length, i, j, dest): # Return if current node is already # visited or it is out of bounds if (i < 0 or j < 0 or i == len(mat) or j == len(mat[0]) or visited[i][j]): return # If reached the destination # then update maximum length if (i == dest[0] and j == dest[1]): # Update max maxi[0] = max(maxi[0], length) return # Mark current node as visited visited[i][j] = True # Recursive call in all # the four directions dfs(mat, maxi, visited, length + 1, i, j - 1, dest) dfs(mat, maxi, visited, length + 1, i + 1, j, dest) dfs(mat, maxi, visited, length + 1, i - 1, j, dest) dfs(mat, maxi, visited, length + 1, i, j + 1, dest) # Mark current cell as unvisited visited[i][j] = False # Function to find the length of # the longest path between two nodes def longestPath(mat, src, dest): # Initialize a variable to # calculate longest path maxi = [0]*1 maxi[0] = 0 # Number of rows N = len(mat) # Number of columns M = len(mat[0]) # Initialize a boolean matrix to # keep track of the cells visited visited = [[0 for x in range(M)] for y in range(N)] # Call the depth-first-search dfs(mat, maxi, visited, 0, src[0], src[1], dest) # Return the answer return maxi[0] + 1 # Driver code if __name__ == "__main__": mat = [[5, 6, 7, 8], [4, 1, 0, 9], [3, 2, 11, 10]] src = [1, 1] dest = [2, 2] print(longestPath(mat, src, dest)) # This code is contributed by ukasp.
C#
// C# implementation for the above approach
using System;
// Driver code
class GFG {
// Function to find the length of
// the longest path between two nodes
public static int longestPath(int[,] mat, int[] src,
int[] dest)
{
// Initialize a variable to
// calculate longest path
int[] max = new int[1];
// Number of rows
int N = mat.GetLength(0);
// Number of columns
int M = mat.GetLength(1);
// Initialize a boolean matrix to
// keep track of the cells visited
bool[,] visited = new bool[N, M];
// Call the depth-first-search
dfs(mat, max, visited, 0, src[0], src[1], dest);
// Return the answer
return max[0] + 1;
}
// Depth-First-Search function for
// recursion and backtracking
public static void dfs(int[,] mat, int[] max,
bool[,] visited, int len,
int i, int j, int[] dest)
{
// Return if current node is already
// visited or it is out of bounds
if (i < 0 || j < 0 || i == mat.GetLength(0)
|| j == mat.GetLength(1)|| visited[i, j])
return;
// If reached the destination
// then update maximum length
if (i == dest[0] && j == dest[1]) {
// Update max
max[0] = Math.Max(max[0], len);
return;
}
// Mark current node as visited
visited[i, j] = true;
// Recursive call in all
// the four directions
dfs(mat, max, visited, len + 1, i, j - 1, dest);
dfs(mat, max, visited, len + 1, i + 1, j, dest);
dfs(mat, max, visited, len + 1, i - 1, j, dest);
dfs(mat, max, visited, len + 1, i, j + 1, dest);
// Mark current cell as unvisited
visited[i, j] = false;
}
// Driver code
public static void Main()
{
int[,] mat = { { 5, 6, 7, 8 },
{ 4, 1, 0, 9 },
{ 3, 2, 11, 10 } };
int[] src = { 1, 1 };
int[] dest = { 2, 2 };
Console.Write(longestPath(mat, src, dest));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Javascript implementation for the above approach
// Depth-First-Search function for
// recursion and backtracking
function dfs(mat, maxi, visited, len, i, j, dest) {
// Return if current node is already
// visited or it is out of bounds
if (i < 0 || j < 0 || i == mat.length || j == mat[0].length || visited[i][j])
return;
// If reached the destination
// then update maximum length
if (i == dest[0] && j == dest[1]) {
// Update max
maxi[0] = Math.max(maxi[0], len);
return;
}
// Mark current node as visited
visited[i][j] = true;
// Recursive call in all
// the four directions
dfs(mat, maxi, visited, len + 1, i, j - 1, dest);
dfs(mat, maxi, visited, len + 1, i + 1, j, dest);
dfs(mat, maxi, visited, len + 1, i - 1, j, dest);
dfs(mat, maxi, visited, len + 1, i, j + 1, dest);
// Mark current cell as unvisited
visited[i][j] = false;
}
// Function to find the length of
// the longest path between two nodes
function longestPath(mat, src, dest) {
// Initialize a variable to
// calculate longest path
let maxi = new Array(1);
maxi[0] = 0;
// Number of rows
let N = mat.length;
// Number of columns
let M = mat[0].length;
// Initialize a boolean matrix to
// keep track of the cells visited
let visited = new Array(N).fill(0).map(() => new Array(M).fill(0));
// Call the depth-first-search
dfs(mat, maxi, visited, 0, src[0], src[1], dest);
// Return the answer
return maxi[0] + 1;
}
// Driver code
let mat = [[5, 6, 7, 8], [4, 1, 0, 9], [3, 2, 11, 1]];
let src = [1, 1];
let dest = [2, 2];
document.write(longestPath(mat, src, dest));
// This code is contributed by gfgking
</script>
Producción
11
Complejidad de Tiempo: O(4 (N+M) )
Espacio Auxiliar: O(N * M)
Publicación traducida automáticamente
Artículo escrito por agarwalakshay107 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA