Dada una array 2D arr[][] de tamaño M*N que contiene 1 y 0 , donde 1 representa que la celda se puede visitar y 0 representa que la celda está bloqueada. Hay un punto de origen (x, y) y la tarea es imprimir todas las rutas desde el origen dado a cualquiera de las cuatro esquinas de la array (0, 0), (0, N – 1), (M – 1 , 0) y (M – 1, N – 1) .
Ejemplos:
Entrada: array[][] ={{1, 0, 0, 1, 0, 0, 1, 1}, {1, 1, 1, 0, 0, 0, 1, 0}, {1, 0, 1, 1, 1, 1, 1, 0}, {0, 0, 0, 0, 1, 0, 0, 0}, {1, 0, 1, 0, 1, 0, 0, 1}, { 0, 1, 1, 1, 1, 0, 0, 1}, {0, 1, 0, 0, 1, 1, 1, 1}, {1, 1, 0, 0, 0, 0, 0, 1} }. fuente = {4, 2}
Salida: {“DRRUUURRUUR”, “DRRUUULLULLU”, “DRRDRRRD”, “DLDDL”}
Explicación: Todos los caminos posibles desde la fuente hasta las 4 esquinas son
Entrada: arr[][] = {{0, 1, 0}, {0, 0, 0}, {0, 0, 0}}, fuente = {0, 1} Salida: No hay
ruta posible
Enfoque: la idea es utilizar la recursividad y el retroceso para encontrar todos los caminos posibles considerando cada camino posible desde un origen a un destino y almacenarlo si es un camino válido. Siga los pasos a continuación para resolver el problema:
- Inicialice un vector de strings ans[] para almacenar la respuesta.
- Llame recursivamente a la función para verificar en cada una de las 4 direcciones mientras presiona la dirección actual y hace que la celda sea visitada.
- Si el puntero cruza el límite o la celda a visitar no es una celda válida, es decir, su valor es 0 , entonces regrese.
- De lo contrario, almacene la celda actual y al llegar a cualquiera de los extremos, luego hágalo como uno de los resultados.
- Después de realizar los pasos anteriores, imprima la array ans[] .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
struct direction {
int x, y;
char c;
};
// Function to check if we reached on
// of the entry/exit (corner) point.
bool isCorner(int i, int j, int M, int N)
{
if ((i == 0 && j == 0)
|| (i == 0 && j == N - 1)
|| (i == M - 1 && j == N - 1)
|| (i == M - 1 && j == 0))
return true;
return false;
}
// Function to check if the index is
// within the matrix boundary.
bool isValid(int i, int j, int M, int N)
{
if (i < 0 || i >= M || j < 0 || j >= N)
return false;
return true;
}
// Recursive helper function
void solve(int i, int j, int M, int N,
direction dir[],
vector<vector<int> >& maze,
string& t, vector<string>& ans)
{
// If any corner is reached push the
// string t into ans and return
if (isCorner(i, j, M, N)) {
ans.push_back(t);
return;
}
// For all the four directions
for (int k = 0; k < 4; k++) {
// The new ith index
int x = i + dir[k].x;
// The new jth index
int y = j + dir[k].y;
// The direction R/L/U/D
char c = dir[k].c;
// If the new cell is within the
// matrix boundary and it is not
// previously visited in same path
if (isValid(x, y, M, N)
&& maze[x][y] == 1) {
// Mark the new cell as visited
maze[x][y] = 0;
// Store the direction
t.push_back(c);
// Recur
solve(x, y, M, N, dir,
maze, t, ans);
// Backtrack to explore
// other paths
t.pop_back();
maze[x][y] = 1;
}
}
return;
}
// Function to find all possible paths
vector<string> possiblePaths(
vector<int> src, vector<vector<int> >& maze)
{
// Create a direction array for all
// the four directions
direction dir[4] = { { -1, 0, 'U' },
{ 0, 1, 'R' },
{ 1, 0, 'D' },
{ 0, -1, 'L' } };
// Stores the result
string temp;
vector<string> ans;
solve(src[0], src[1], maze.size(),
maze[0].size(), dir,
maze, temp, ans);
return ans;
}
// Driver Code
int main()
{
// Initializing the variables
vector<vector<int> > maze = {
{ 1, 0, 0, 1, 0, 0, 1, 1 },
{ 1, 1, 1, 0, 0, 0, 1, 0 },
{ 1, 0, 1, 1, 1, 1, 1, 0 },
{ 0, 0, 0, 0, 1, 0, 0, 0 },
{ 1, 0, 1, 0, 1, 0, 0, 1 },
{ 0, 1, 1, 1, 1, 0, 0, 1 },
{ 0, 1, 0, 0, 1, 1, 1, 1 },
{ 1, 1, 0, 0, 0, 0, 0, 1 },
};
vector<int> src = { 4, 2 };
// Function Call
vector<string> paths
= possiblePaths(src, maze);
// Print the result
if (paths.size() == 0) {
cout << "No Possible Paths";
return 0;
}
for (int i = 0; i < paths.size(); i++)
cout << paths[i] << endl;
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class GFG {
static class direction {
int x, y;
char c;
direction(int x, int y, char c)
{
this.c = c;
this.x = x;
this.y = y;
}
};
// Function to check if we reached on
// of the entry/exit (corner) point.
static boolean isCorner(int i, int j, int M, int N)
{
if ((i == 0 && j == 0) || (i == 0 && j == N - 1)
|| (i == M - 1 && j == N - 1)
|| (i == M - 1 && j == 0))
return true;
return false;
}
// Function to check if the index is
// within the matrix boundary.
static boolean isValid(int i, int j, int M, int N)
{
if (i < 0 || i >= M || j < 0 || j >= N)
return false;
return true;
}
// Recursive helper function
static void solve(int i, int j, int M, int N,
direction dir[], int[][] maze,
String t, ArrayList<String> ans)
{
// If any corner is reached push the
// string t into ans and return
if (isCorner(i, j, M, N)) {
ans.add(t);
return;
}
// For all the four directions
for (int k = 0; k < 4; k++) {
// The new ith index
int x = i + dir[k].x;
// The new jth index
int y = j + dir[k].y;
// The direction R/L/U/D
char c = dir[k].c;
// If the new cell is within the
// matrix boundary and it is not
// previously visited in same path
if (isValid(x, y, M, N) && maze[x][y] == 1) {
// Mark the new cell as visited
maze[x][y] = 0;
// Store the direction
t += c;
// Recur
solve(x, y, M, N, dir, maze, t, ans);
// Backtrack to explore
// other paths
t = t.substring(0, t.length() - 1);
maze[x][y] = 1;
}
}
return;
}
// Function to find all possible paths
static ArrayList<String> possiblePaths(int[] src,
int[][] maze)
{
// Create a direction array for all
// the four directions
direction[] dir = { new direction(-1, 0, 'U'),
new direction(0, 1, 'R'),
new direction(1, 0, 'D'),
new direction(0, -1, 'L') };
// Stores the result
String temp = "";
ArrayList<String> ans = new ArrayList<>();
solve(src[0], src[1], maze.length, maze[0].length,
dir, maze, temp, ans);
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Initializing the variables
int[][] maze = {
{ 1, 0, 0, 1, 0, 0, 1, 1 },
{ 1, 1, 1, 0, 0, 0, 1, 0 },
{ 1, 0, 1, 1, 1, 1, 1, 0 },
{ 0, 0, 0, 0, 1, 0, 0, 0 },
{ 1, 0, 1, 0, 1, 0, 0, 1 },
{ 0, 1, 1, 1, 1, 0, 0, 1 },
{ 0, 1, 0, 0, 1, 1, 1, 1 },
{ 1, 1, 0, 0, 0, 0, 0, 1 },
};
int[] src = { 4, 2 };
// Function Call
ArrayList<String> paths = possiblePaths(src, maze);
// Print the result
if (paths.size() == 0) {
System.out.println("No Possible Paths");
return;
}
for (int i = 0; i < paths.size(); i++) {
System.out.println(paths.get(i));
}
}
}
// This code is contributed by Karandeep1234
Python3
# Python program for the above approach
# Function to check if we reached on
# of the entry/exit (corner) point.
def isCorner(i, j, M, N):
if((i == 0 and j == 0) or (i == 0 and j == N-1) or (i == M-1 and j == N-1) or (i == M-1 and j == 0)):
return True
return False
# Function to check if the index is
# within the matrix boundary.
def isValid(i, j, M, N):
if(i < 0 or i >= M or j < 0 or j >= N):
return False
return True
# Recursive helper function
def solve(i, j, M, N, Dir, maze, t, ans):
# If any corner is reached push the
# string t into ans and return
if(isCorner(i, j, M, N)):
ans.append(t)
return
# For all the four directions
for k in range(4):
# The new ith index
x = i + Dir[k][0]
# The new jth index
y = j + Dir[k][1]
# The direction R/L/U/D
c = Dir[k][2]
# If the new cell is within the
# matrix boundary and it is not
# previously visited in same path
if(isValid(x, y, M, N) and maze[x][y] == 1):
# mark the new cell visited
maze[x][y] = 0
# Store the direction
t += c
solve(x, y, M, N, Dir, maze, t, ans)
# Backtrack to explore
# other paths
t = t[: len(t)-1]
maze[x][y] = 1
return
# Function to find all possible paths
def possiblePaths(src, maze):
# Create a direction array for all
# the four directions
Dir = [[-1, 0, 'U'], [0, 1, 'R'], [1, 0, 'D'], [0, -1, 'L']]
# stores the result
temp = ""
ans = []
solve(src[0], src[1], len(maze), len(maze[0]), Dir, maze, temp, ans)
return ans
# Driver code
# Initialise variable
maze = [[1, 0, 0, 1, 0, 0, 1, 1],
[1, 1, 1, 0, 0, 0, 1, 0],
[1, 0, 1, 1, 1, 1, 1, 0],
[0, 0, 0, 0, 1, 0, 0, 0],
[1, 0, 1, 0, 1, 0, 0, 1],
[0, 1, 1, 1, 1, 0, 0, 1],
[0, 1, 0, 0, 1, 1, 1, 1],
[1, 1, 0, 0, 0, 0, 0, 1]]
src = [4, 2]
# function call
paths = possiblePaths(src, maze)
# Print the result
if(len(paths) == 0):
print("No Possible Paths")
else:
for i in paths:
print(i)
# This code is contributed by parthmanchanda81
Javascript
<script>
// Javascript program for the above approach
// Function to check if we reached on
// of the entry/exit (corner) point.
function isCorner(i, j, M, N) {
if (
(i == 0 && j == 0) ||
(i == 0 && j == N - 1) ||
(i == M - 1 && j == N - 1) ||
(i == M - 1 && j == 0)
)
return true;
return false;
}
// Function to check if the index is
// within the matrix boundary.
function isValid(i, j, M, N) {
if (i < 0 || i >= M || j < 0 || j >= N) return false;
return true;
}
// Recursive helper function
function solve(i, j, M, N, Dir, maze, t, ans) {
// If any corner is reached push the
// string t into ans and return
if (isCorner(i, j, M, N)) {
ans.push(t);
return;
}
// For all the four directions
for (let k = 0; k < 4; k++) {
// The new ith index
let x = i + Dir[k][0];
// The new jth index
let y = j + Dir[k][1];
// The direction R/L/U/D
let c = Dir[k][2];
// If the new cell is within the
// matrix boundary and it is not
// previously visited in same path
if (isValid(x, y, M, N) && maze[x][y] == 1) {
// mark the new cell visited
maze[x][y] = 0;
// Store the direction
t += c;
solve(x, y, M, N, Dir, maze, t, ans);
// Backtrack to explore
// other paths
t = t.substr(0, t.length - 1);
maze[x][y] = 1;
}
}
return;
}
// Function to find all possible paths
function possiblePaths(src, maze) {
// Create a direction array for all
// the four directions
let Dir = [
[-1, 0, "U"],
[0, 1, "R"],
[1, 0, "D"],
[0, -1, "L"],
];
// stores the result
let temp = "";
let ans = [];
solve(src[0], src[1], maze.length, maze[0].length, Dir, maze, temp, ans);
return ans;
}
// Driver code
// Initialise variable
let maze = [
[1, 0, 0, 1, 0, 0, 1, 1],
[1, 1, 1, 0, 0, 0, 1, 0],
[1, 0, 1, 1, 1, 1, 1, 0],
[0, 0, 0, 0, 1, 0, 0, 0],
[1, 0, 1, 0, 1, 0, 0, 1],
[0, 1, 1, 1, 1, 0, 0, 1],
[0, 1, 0, 0, 1, 1, 1, 1],
[1, 1, 0, 0, 0, 0, 0, 1],
];
let src = [4, 2];
// function call
let paths = possiblePaths(src, maze);
// Print the result
if (paths.length == 0) {
document.write("No Possible Paths");
} else {
for (let i = 0; i < paths.length; i++) {
if (paths[i]) document.write(paths[i] + "<Br>");
}
}
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
DRRUUURRUUR DRRUUULLULLU DRRDRRRD DLDDL
Complejidad de tiempo: O(3 (M*N) )
Espacio auxiliar: O(3 (M*N) )