Ruta más larga posible en una array con obstáculos

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

Deja una respuesta

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