Una variación de rata en un laberinto .
Se le da un laberinto en forma de array N * N 2-D (llamémoslo M), hay una rata en la celda superior izquierda, es decir , M[0][0] y hay una puerta de escape en la celda inferior derecha es decir , M[N-1][N-1] . Desde cada celda M[i][j] (0 ≤ i ≤ N-1, 0 ≤ j ≤ N-1) la rata puede dar un número de pasos hacia su derecha (por ejemplo: a M[i][j+ s ]), o un número de pasos hacia abajo (por ejemplo: a M[i+ s][j]), donde el número máximo de pasos (o el valor máximo de s) puede ser el valor en la celda M[i][j ] . Si alguna celda contiene 0 , entonces es un callejón sin salida . Por ejemplo:En la segunda imagen de la figura a continuación, la rata en M[0][0] puede saltar a una celda: M[0][1] , M[0][2] , M[1][0] o M [2][0] .
Tienes que imprimir un camino posible de M[0][0] a M[N-1][N-1] en forma de array de tamaño N * N tal que las celdas que están en el camino tengan un valor 1 y otras celdas tienen un valor 0 . Para el ejemplo anterior, una de esas soluciones es:
Hay una solución de retroceso para este problema en este artículo .
Aquí se presenta una solución basada en Programación Dinámica.
Ejemplos:
Entrada: mat[][] = {
{3, 0, 0, 2, 1},
{0, 0, 0, 0, 2},
{0, 1, 0, 1, 0},
{1, 0, 0, 1, 1},
{3, 0, 0, 1, 1} }
Salida:
1 0 0 1 1
0 0 0 0 1
0 0 0 0 0
0 0 0 0 1
0 0 0 0 1
Entrada: mat[ ][] = { {0, 0}, {0, 1} }
Salida: No existe ruta
Acercarse:
- Inicialice una array booleana CRF[N][N] (puede alcanzar desde) con false . Ahora haga CRF[N – 1][N – 1] = verdadero ya que se puede llegar al destino desde el destino.
- Ahora, comenzando desde laberinto[N – 1][N – 1] y terminando en laberinto[0][0], actualice todas las celdas en CRF[][] según sea posible llegar a cualquier otra celda válida (lo que lleva a el destino).
- Cuando se haya actualizado toda la array CRF[][] , use para crear una array que contenga todos los 1 en las celdas en la ruta que conduce al destino y otras celdas son 0 .
- Imprima esta array recién creada al final.
- Si no es posible llegar al destino, imprima No existe ninguna ruta .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to check whether the path exists
bool hasPath(vector<vector<int>> maze, vector<vector<int>>& sol,
int N)
{
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
sol[i][j] = 0;
// Declaring and initializing CRF
// (can reach from) matrix
vector<vector<bool>> CRF(N);
for (int i = 0; i < N; i++)
CRF[i] = vector<bool>(N);
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
CRF[i][j] = false;
CRF[N - 1][N - 1] = true;
// Using the DP to fill CRF matrix
// in correct order
for (int k = N - 1; k >= 0; k--) {
for (int j = k; j >= 0; j--) {
if (!(k == N - 1 && j == N - 1)) {
// If it is possible to get
// to a valid location from
// cell maze[k][j]
for (int a = 0; a <= maze[k][j]; a++) {
if ((j + a < N && CRF[k][j + a] == true)
|| (k + a < N && CRF[k + a][j] == true)) {
CRF[k][j] = true;
break;
}
}
// If it is possible to get to
// a valid location from cell
// maze[j][k]
for (int a = 0; a <= maze[j][k]; a++) {
if ((k + a < N && CRF[j][k + a] == true)
|| (j + a < N && CRF[j + a][k] == true)) {
CRF[j][k] = true;
break;
}
}
}
}
}
// If CRF[0][0] is false it means we cannot reach
// the end of the maze at all
if (CRF[0][0] == false)
return false;
// Filling the solution matrix using CRF
int i = 0, j = 0;
while (!(i == N - 1 && j == N - 1)) {
sol[i][j] = 1;
if (maze[i][j] > 0)
// Get to a valid location from
// the current cell
for (int a = 1; a <= maze[i][j]; a++) {
if ((j + a < N && CRF[i][j + a] == true)) {
j = j + a;
break;
}
else if ((i + a < N && CRF[i + a][j] == true)) {
i = i + a;
break;
}
}
}
sol[N - 1][N - 1] = 1;
return true;
}
// Utility function to print the contents
// of a 2-D array
void printMatrix(vector<vector<int>> sol, int N)
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
cout << sol[i][j] << " ";
cout << "\n";
}
}
// Driver code
int main()
{
vector<vector<int>> maze = { { 2, 2, 1, 1, 0 },
{ 0, 0, 3, 0, 0 },
{ 1, 0, 0, 0, 0 },
{ 0, 0, 2, 0, 1 },
{ 0, 0, 3, 0, 0 } };
int N = maze.size();
vector<vector<int>> sol(N,vector<int>(N));
// If path exists
if (hasPath(maze, sol, N))
// Print the path
printMatrix(sol, N);
else
cout << "No path exists";
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static int MAX = 50;
// Function to check whether the path exists
static boolean hasPath(int maze[][],
int sol[][], int N)
{
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
sol[i][j] = 0;
// Declaring and initializing CRF
// (can reach from) matrix
boolean [][]CRF = new boolean[N][N];
CRF[N - 1][N - 1] = true;
// Using the DP to fill CRF matrix
// in correct order
for (int k = N - 1; k >= 0; k--)
{
for (int j = k; j >= 0; j--)
{
if (!(k == N - 1 && j == N - 1))
{
// If it is possible to get
// to a valid location from
// cell maze[k][j]
for (int a = 0; a <= maze[k][j]; a++)
{
if ((j + a < N && CRF[k][j + a] == true) ||
(k + a < N && CRF[k + a][j] == true))
{
CRF[k][j] = true;
break;
}
}
// If it is possible to get to
// a valid location from cell
// maze[j][k]
for (int a = 0; a <= maze[j][k]; a++)
{
if ((k + a < N && CRF[j][k + a] == true) ||
(j + a < N && CRF[j + a][k] == true))
{
CRF[j][k] = true;
break;
}
}
}
}
}
// If CRF[0][0] is false it means we cannot reach
// the end of the maze at all
if (CRF[0][0] == false)
return false;
// Filling the solution matrix using CRF
int i = 0, j = 0;
while (!(i == N - 1 && j == N - 1))
{
sol[i][j] = 1;
if (maze[i][j] > 0)
// Get to a valid location from
// the current cell
for (int a = 1; a <= maze[i][j]; a++)
{
if ((j + a < N && CRF[i][j + a] == true))
{
j = j + a;
break;
}
else if ((i + a < N && CRF[i + a][j] == true))
{
i = i + a;
break;
}
}
}
sol[N - 1][N - 1] = 1;
return true;
}
// Utility function to print the contents
// of a 2-D array
static void printMatrix(int sol[][], int N)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
System.out.print(sol[i][j] + " ");
System.out.println();
}
}
// Driver code
public static void main(String[] args)
{
int maze[][] = {{ 2, 2, 1, 1, 0 },
{ 0, 0, 3, 0, 0 },
{ 1, 0, 0, 0, 0 },
{ 0, 0, 2, 0, 1 },
{ 0, 0, 3, 0, 0 }};
int N = maze.length;
int [][]sol = new int [N][MAX];
// If path exists
if (hasPath(maze, sol, N))
// Print the path
printMatrix(sol, N);
else
System.out.println("No path exists");
}
}
// This code is contributed by Princi Singh
C#
// C# implementation of the approach
using System;
class GFG
{
static int MAX = 50;
// Function to check whether the path exists
static Boolean hasPath(int [,]maze,
int [,]sol, int N)
{
int i, j, k;
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
sol[i, j] = 0;
// Declaring and initializing CRF
// (can reach from) matrix
Boolean [,]CRF = new Boolean[N, N];
CRF[N - 1, N - 1] = true;
// Using the DP to fill CRF matrix
// in correct order
for (k = N - 1; k >= 0; k--)
{
for (j = k; j >= 0; j--)
{
if (!(k == N - 1 && j == N - 1))
{
// If it is possible to get
// to a valid location from
// cell maze[k,j]
for (int a = 0; a <= maze[k, j]; a++)
{
if ((j + a < N && CRF[k, j + a] == true) ||
(k + a < N && CRF[k + a, j] == true))
{
CRF[k, j] = true;
break;
}
}
// If it is possible to get to
// a valid location from cell
// maze[j,k]
for (int a = 0; a <= maze[j, k]; a++)
{
if ((k + a < N && CRF[j, k + a] == true) ||
(j + a < N && CRF[j + a, k] == true))
{
CRF[j, k] = true;
break;
}
}
}
}
}
// If CRF[0,0] is false it means we cannot
// reach the end of the maze at all
if (CRF[0, 0] == false)
return false;
// Filling the solution matrix using CRF
i = 0; j = 0;
while (!(i == N - 1 && j == N - 1))
{
sol[i, j] = 1;
if (maze[i, j] > 0)
// Get to a valid location from
// the current cell
for (int a = 1; a <= maze[i, j]; a++)
{
if ((j + a < N &&
CRF[i, j + a] == true))
{
j = j + a;
break;
}
else if ((i + a < N &&
CRF[i + a, j] == true))
{
i = i + a;
break;
}
}
}
sol[N - 1, N - 1] = 1;
return true;
}
// Utility function to print the contents
// of a 2-D array
static void printMatrix(int [,]sol, int N)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
Console.Write(sol[i, j] + " ");
Console.WriteLine();
}
}
// Driver code
public static void Main(String[] args)
{
int [,]maze = {{ 2, 2, 1, 1, 0 },
{ 0, 0, 3, 0, 0 },
{ 1, 0, 0, 0, 0 },
{ 0, 0, 2, 0, 1 },
{ 0, 0, 3, 0, 0 }};
int N = maze.GetLength(0);
int [,]sol = new int [N, MAX];
// If path exists
if (hasPath(maze, sol, N))
// Print the path
printMatrix(sol, N);
else
Console.WriteLine("No path exists");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation of the approach
var MAX = 50;
// Function to check whether the path exists
function hasPath(maze, sol, N)
{
for (var i = 0; i < N; i++)
for (var j = 0; j < N; j++)
sol[i][j] = 0;
// Declaring and initializing CRF
// (can reach from) matrix
var CRF = Array.from(Array(N), ()=>Array(N));;
for (var i = 0; i < N; i++)
for (var j = 0; j < N; j++)
CRF[i][j] = false;
CRF[N - 1][N - 1] = true;
// Using the DP to fill CRF matrix
// in correct order
for (var k = N - 1; k >= 0; k--) {
for (var j = k; j >= 0; j--) {
if (!(k == N - 1 && j == N - 1)) {
// If it is possible to get
// to a valid location from
// cell maze[k][j]
for (var a = 0; a <= maze[k][j]; a++) {
if ((j + a < N && CRF[k][j + a] == true)
|| (k + a < N && CRF[k + a][j] == true)) {
CRF[k][j] = true;
break;
}
}
// If it is possible to get to
// a valid location from cell
// maze[j][k]
for (var a = 0; a <= maze[j][k]; a++) {
if ((k + a < N && CRF[j][k + a] == true)
|| (j + a < N && CRF[j + a][k] == true)) {
CRF[j][k] = true;
break;
}
}
}
}
}
// If CRF[0][0] is false it means we cannot reach
// the end of the maze at all
if (CRF[0][0] == false)
return false;
// Filling the solution matrix using CRF
var i = 0, j = 0;
while (!(i == N - 1 && j == N - 1)) {
sol[i][j] = 1;
if (maze[i][j] > 0)
// Get to a valid location from
// the current cell
for (var a = 1; a <= maze[i][j]; a++) {
if ((j + a < N && CRF[i][j + a] == true)) {
j = j + a;
break;
}
else if ((i + a < N && CRF[i + a][j] == true)) {
i = i + a;
break;
}
}
}
sol[N - 1][N - 1] = 1;
return true;
}
// Utility function to print the contents
// of a 2-D array
function printMatrix( sol, N)
{
for (var i = 0; i < N; i++) {
for (var j = 0; j < N; j++)
document.write( sol[i][j] + " ");
document.write("<br>");
}
}
// Driver code
var maze = [ [ 2, 2, 1, 1, 0 ],
[ 0, 0, 3, 0, 0 ],
[ 1, 0, 0, 0, 0 ],
[ 0, 0, 2, 0, 1 ],
[ 0, 0, 3, 0, 0 ] ];
var N = maze.length;
var sol = Array.from(Array(N), ()=>Array(MAX));
// If path exists
if (hasPath(maze, sol, N))
// Print the path
printMatrix(sol, N);
else
document.write( "No path exists");
</script>
Python3
# Python3 implementation of the approach
MAX=50
# Function to check whether the path exists
def hasPath(maze, sol,N):
for i in range(N):
for j in range(N):
sol[i][j] = 0
# Declaring and initializing CRF
# can reach from matrix
CRF =[[False]*N for _ in range(N)]
for i in range(N):
for j in range(N):
CRF[i][j] = False
CRF[N - 1][N - 1] = True
# Using the DP to fill CRF matrix
# in correct order
for k in range(N-1,-1,-1):
for j in range(k,-1,-1):
if not(k == N - 1 and j == N - 1):
# If it is possible to get
# to a valid location from
# cell maze[k][j]
for a in range(maze[k][j]+1):
if (j + a < N and CRF[k][j + a]) or (k + a < N and CRF[k + a][j]):
CRF[k][j] = True
break
# If it is possible to get to
# a valid location from cell
# maze[j][k]
for a in range(maze[j][k]+1):
if ((k + a < N and CRF[j][k + a]) or (j + a < N and CRF[j + a][k])):
CRF[j][k] = True
break
# If CRF[0][0] is false it means we cannot reach
# the end of the maze at all
if not CRF[0][0]:
return False
# Filling the solution matrix using CRF
i = 0; j = 0
while (not (i == N - 1 and j == N - 1)):
sol[i][j] = 1
if (maze[i][j] > 0):
# Get to a valid location from
# the current cell
for a in range(1,maze[i][j]+1):
if (j + a < N and CRF[i][j + a]):
j = j + a
break
elif ((i + a < N and CRF[i + a][j])):
i = i + a
break
sol[N - 1][N - 1] = 1
return True
# Utility function to print the contents
# of a 2-D array
def printMatrix(sol, N):
for i in range(N):
for j in range(N):
print(sol[i][j],end=" ")
print()
# Driver code
if __name__ == '__main__':
maze= [ [ 2, 2, 1, 1, 0 ],
[ 0, 0, 3, 0, 0 ],
[ 1, 0, 0, 0, 0 ],
[ 0, 0, 2, 0, 1 ],
[ 0, 0, 3, 0, 0 ] ]
N = len(maze)
sol=[[0]*N for _ in range(MAX)]
# If path exists
if (hasPath(maze, sol, N)):
# Print the path
printMatrix(sol, N)
else:
print("No path exists")
# This code is contributed by Amartya Ghosh
Producción:
1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1
Complejidad temporal: O(N ^ 2 * MAX), donde N es el número de filas y MAX es el elemento máximo de la array.
Espacio Auxiliar: O(N * N)
Publicación traducida automáticamente
Artículo escrito por Jaideep Sagar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA