Dada una array M x N, con algunos obstáculos colocados arbitrariamente, calcule la longitud de la ruta más larga posible desde el origen hasta el destino dentro de la array. Solo se nos permite movernos a celdas adyacentes que no son obstáculos. La ruta no puede contener movimientos diagonales y una ubicación que se haya visitado una vez en una ruta en particular no se puede volver a visitar.
Por ejemplo, el camino más largo sin obstáculos desde el origen hasta el destino se destaca a continuación. La longitud del camino es 24.
La idea es usar Backtracking. Comenzamos desde la celda de origen de la array, avanzamos en las cuatro direcciones permitidas y verificamos recursivamente si conducen a la solución o no. Si se encuentra el destino, actualizamos el valor de la ruta más larga; de lo contrario, si ninguna de las soluciones anteriores funciona, devolvemos falso desde nuestra función.
A continuación se muestra la implementación de la idea anterior.
CPP
// C++ program to find Longest Possible Route in a
// matrix with hurdles
#include <bits/stdc++.h>
using namespace std;
#define R 3
#define C 10
// A Pair to store status of a cell. found is set to
// true of destination is reachable and value stores
// distance of longest path
struct Pair {
// true if destination is found
bool found;
// stores cost of longest path from current cell to
// destination cell
int value;
};
// Function to find Longest Possible Route in the
// matrix with hurdles. If the destination is not reachable
// the function returns false with cost INT_MAX.
// (i, j) is source cell and (x, y) is destination cell.
Pair findLongestPathUtil(int mat[R][C], int i, int j, int x,
int y, bool visited[R][C])
{
// if (i, j) itself is destination, return true
if (i == x && j == y) {
Pair p = { true, 0 };
return p;
}
// if not a valid cell, return false
if (i < 0 || i >= R || j < 0 || j >= C || mat[i][j] == 0
|| visited[i][j]) {
Pair p = { false, INT_MAX };
return p;
}
// include (i, j) in current path i.e.
// set visited(i, j) to true
visited[i][j] = true;
// res stores longest path from current cell (i, j) to
// destination cell (x, y)
int res = INT_MIN;
// go left from current cell
Pair sol
= findLongestPathUtil(mat, i, j - 1, x, y, visited);
// if destination can be reached on going left from
// current cell, update res
if (sol.found)
res = max(res, sol.value);
// go right from current cell
sol = findLongestPathUtil(mat, i, j + 1, x, y, visited);
// if destination can be reached on going right from
// current cell, update res
if (sol.found)
res = max(res, sol.value);
// go up from current cell
sol = findLongestPathUtil(mat, i - 1, j, x, y, visited);
// if destination can be reached on going up from
// current cell, update res
if (sol.found)
res = max(res, sol.value);
// go down from current cell
sol = findLongestPathUtil(mat, i + 1, j, x, y, visited);
// if destination can be reached on going down from
// current cell, update res
if (sol.found)
res = max(res, sol.value);
// Backtrack
visited[i][j] = false;
// if destination can be reached from current cell,
// return true
if (res != INT_MIN) {
Pair p = { true, 1 + res };
return p;
}
// if destination can't be reached from current cell,
// return false
else {
Pair p = { false, INT_MAX };
return p;
}
}
// A wrapper function over findLongestPathUtil()
void findLongestPath(int mat[R][C], int i, int j, int x,
int y)
{
// create a boolean matrix to store info about
// cells already visited in current route
bool visited[R][C];
// initialize visited to false
memset(visited, false, sizeof visited);
// find longest route from (i, j) to (x, y) and
// print its maximum cost
Pair p = findLongestPathUtil(mat, i, j, x, y, visited);
if (p.found)
cout << "Length of longest possible route is "
<< p.value;
// If the destination is not reachable
else
cout << "Destination not reachable from given "
"source";
}
// Driver code
int main()
{
// input matrix with hurdles shown with number 0
int mat[R][C] = { { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 0, 1, 1, 0, 1, 1, 0, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } };
// find longest path with source (0, 0) and
// destination (1, 7)
findLongestPath(mat, 0, 0, 1, 7);
return 0;
}
Java
// Java program to find Longest Possible Route in a
// matrix with hurdles
import java.io.*;
class GFG {
static int R = 3;
static int C = 10;
// A Pair to store status of a cell. found is set to
// true of destination is reachable and value stores
// distance of longest path
static class Pair {
// true if destination is found
boolean found;
// stores cost of longest path from current cell to
// destination cell
int val;
Pair (boolean x, int y){
found = x;
val = y;
}
}
// Function to find Longest Possible Route in the
// matrix with hurdles. If the destination is not reachable
// the function returns false with cost Integer.MAX_VALUE.
// (i, j) is source cell and (x, y) is destination cell.
static Pair findLongestPathUtil (int mat[][], int i, int j, int x, int y, boolean visited[][]) {
// if (i, j) itself is destination, return true
if(i == x && j == y)
return new Pair(true, 0);
// if not a valid cell, return false
if(i < 0 || i >= R || j < 0 || j >= C || mat[i][j] == 0 || visited[i][j] )
return new Pair(false, Integer.MAX_VALUE);
// include (i, j) in current path i.e.
// set visited(i, j) to true
visited[i][j] = true;
// res stores longest path from current cell (i, j) to
// destination cell (x, y)
int res = Integer.MIN_VALUE;
// go left from current cell
Pair sol = findLongestPathUtil(mat, i, j-1, x, y, visited);
// if destination can be reached on going left from current
// cell, update res
if(sol.found)
res = Math.max(sol.val, res);
// go right from current cell
sol = findLongestPathUtil(mat, i, j+1, x, y, visited);
// if destination can be reached on going right from current
// cell, update res
if(sol.found)
res = Math.max(sol.val, res);
// go up from current cell
sol = findLongestPathUtil(mat, i-1, j, x, y, visited);
// if destination can be reached on going up from current
// cell, update res
if(sol.found)
res = Math.max(sol.val, res);
// go down from current cell
sol = findLongestPathUtil(mat, i+1, j, x, y, visited);
// if destination can be reached on going down from current
// cell, update res
if(sol.found)
res = Math.max(sol.val, res);
// Backtrack
visited[i][j] = false;
// if destination can be reached from current cell,
// return true
if(res != Integer.MIN_VALUE)
return new Pair(true, res+1);
// if destination can't be reached from current cell,
// return false
else
return new Pair(false, Integer.MAX_VALUE);
}
// A wrapper function over findLongestPathUtil()
static void findLongestPath (int mat[][], int i, int j, int x, int y) {
// create a boolean matrix to store info about
// cells already visited in current route
boolean visited[][] = new boolean[R][C];
// find longest route from (i, j) to (x, y) and
// print its maximum cost
Pair p = findLongestPathUtil(mat, i, j, x, y, visited);
if(p.found)
System.out.println("Length of longest possible route is " + p.val);
// If the destination is not reachable
else
System.out.println("Destination not reachable from given source");
}
// Driver Code
public static void main (String[] args) {
// input matrix with hurdles shown with number 0
int mat[][] = { { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 0, 1, 1, 0, 1, 1, 0, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } };
// find longest path with source (0, 0) and
// destination (1, 7)
findLongestPath(mat, 0, 0, 1, 7);
}
}
// This code is contributed by th_aditi.
Python3
# Python program to find Longest Possible Route in a
# matrix with hurdles
import sys
R,C = 3,10
# A Pair to store status of a cell. found is set to
# True of destination is reachable and value stores
# distance of longest path
class Pair:
def __init__(self, found, value):
self.found = found
self.value = value
# Function to find Longest Possible Route in the
# matrix with hurdles. If the destination is not reachable
# the function returns false with cost sys.maxsize.
# (i, j) is source cell and (x, y) is destination cell.
def findLongestPathUtil(mat, i, j, x, y, visited):
# if (i, j) itself is destination, return True
if (i == x and j == y):
p = Pair( True, 0 )
return p
# if not a valid cell, return false
if (i < 0 or i >= R or j < 0 or j >= C or mat[i][j] == 0 or visited[i][j]) :
p = Pair( False, sys.maxsize )
return p
# include (i, j) in current path i.e.
# set visited(i, j) to True
visited[i][j] = True
# res stores longest path from current cell (i, j) to
# destination cell (x, y)
res = -sys.maxsize -1
# go left from current cell
sol = findLongestPathUtil(mat, i, j - 1, x, y, visited)
# if destination can be reached on going left from
# current cell, update res
if (sol.found):
res = max(res, sol.value)
# go right from current cell
sol = findLongestPathUtil(mat, i, j + 1, x, y, visited)
# if destination can be reached on going right from
# current cell, update res
if (sol.found):
res = max(res, sol.value)
# go up from current cell
sol = findLongestPathUtil(mat, i - 1, j, x, y, visited)
# if destination can be reached on going up from
# current cell, update res
if (sol.found):
res = max(res, sol.value)
# go down from current cell
sol = findLongestPathUtil(mat, i + 1, j, x, y, visited)
# if destination can be reached on going down from
# current cell, update res
if (sol.found):
res = max(res, sol.value)
# Backtrack
visited[i][j] = False
# if destination can be reached from current cell,
# return True
if (res != -sys.maxsize -1):
p = Pair( True, 1 + res )
return p
# if destination can't be reached from current cell,
# return false
else:
p = Pair( False, sys.maxsize )
return p
# A wrapper function over findLongestPathUtil()
def findLongestPath(mat, i, j, x,y):
# create a boolean matrix to store info about
# cells already visited in current route
# initialize visited to false
visited = [[False for i in range(C)]for j in range(R)]
# find longest route from (i, j) to (x, y) and
# print its maximum cost
p = findLongestPathUtil(mat, i, j, x, y, visited)
if (p.found):
print("Length of longest possible route is ",str(p.value))
# If the destination is not reachable
else:
print("Destination not reachable from given source")
# Driver code
# input matrix with hurdles shown with number 0
mat = [ [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ],
[ 1, 1, 0, 1, 1, 0, 1, 1, 0, 1 ],
[ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ] ]
# find longest path with source (0, 0) and
# destination (1, 7)
findLongestPath(mat, 0, 0, 1, 7)
# This code is contributed by shinjanpatra
C#
// Java program to find Longest Possible Route in a
// matrix with hurdles
using System;
class GFG {
static int R = 3;
static int C = 10;
// Function to find Longest Possible Route in the
// matrix with hurdles. If the destination is not reachable
// the function returns false with cost Integer.MAX_VALUE.
// (i, j) is source cell and (x, y) is destination cell.
static Tuple<bool,int> findLongestPathUtil (int[, ] mat, int i, int j, int x, int y, bool[, ] visited) {
// if (i, j) itself is destination, return true
if(i == x && j == y)
return new Tuple<bool,int>(true, 0);
// if not a valid cell, return false
if(i < 0 || i >= R || j < 0 || j >= C || mat[i,j] == 0 || visited[i,j])
return new Tuple<bool,int>(false, Int32.MaxValue);
// include (i, j) in current path i.e.
// set visited(i, j) to true
visited[i,j] = true;
// res stores longest path from current cell (i, j) to
// destination cell (x, y)
int res = Int32.MinValue;
// go left from current cell
Tuple<bool,int> sol = findLongestPathUtil(mat, i, j-1, x, y, visited);
// if destination can be reached on going left from current
// cell, update res
if(sol.Item1)
res = Math.Max(sol.Item2, res);
// go right from current cell
sol = findLongestPathUtil(mat, i, j+1, x, y, visited);
// if destination can be reached on going right from current
// cell, update res
if(sol.Item1)
res = Math.Max(sol.Item2, res);
// go up from current cell
sol = findLongestPathUtil(mat, i-1, j, x, y, visited);
// if destination can be reached on going up from current
// cell, update res
if(sol.Item1)
res = Math.Max(sol.Item2, res);
// go down from current cell
sol = findLongestPathUtil(mat, i+1, j, x, y, visited);
// if destination can be reached on going down from current
// cell, update res
if(sol.Item1)
res = Math.Max(sol.Item2, res);
// Backtrack
visited[i,j] = false;
// if destination can be reached from current cell,
// return true
if(res != Int32.MinValue)
return new Tuple<bool,int>(true, res+1);
// if destination can't be reached from current cell,
// return false
else
return new Tuple<bool,int>(false, Int32.MaxValue);
}
// A wrapper function over findLongestPathUtil()
static void findLongestPath (int [, ]mat, int i, int j, int x, int y) {
// create a boolean matrix to store info about
// cells already visited in current route
bool[,] visited = new bool[R,C];
// find longest route from (i, j) to (x, y) and
// print its maximum cost
Tuple<bool,int> p = findLongestPathUtil(mat, i, j, x, y, visited);
if(p.Item1)
Console.WriteLine("Length of longest possible route is : " + p.Item2);
// If the destination is not reachable
else
Console.WriteLine("Destination not reachable from given source");
}
// Driver Code
public static void Main() {
// input matrix with hurdles shown with number 0
int[,] mat = new int[,] { { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 0, 1, 1, 0, 1, 1, 0, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } };
// find longest path with source (0, 0) and
// destination (1, 7)
findLongestPath(mat, 0, 0, 1, 7);
}
}
// This code is contributed by Abhijeet Kumar(abhijeet19403)
Producción
Length of longest possible route is 24
Complejidad de tiempo: 4^(R*C)
Aquí R y C son los números de filas y columnas respectivamente. Para cada índice tenemos cuatro opciones, por lo que nuestra complejidad de tiempo total será 4^(R*C).
Espacio Auxiliar: O(R*C)
El espacio adicional se utiliza para almacenar los elementos de la array visitada.
Este artículo es una contribución de Aditya Goel . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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