Requisitos previos : recursividad , retroceso y estructura de datos de pila .
Un Laberinto se da como array binaria N*M de bloques y hay una rata inicialmente en (0, 0), es decir. maze[0][0] y la rata quiere comer comida que está presente en algún bloque dado en el laberinto (fx, fy). En una array de laberinto, 0 significa que el bloque es un callejón sin salida y 1 significa que el bloque se puede utilizar en la ruta desde el origen hasta el destino. La rata puede moverse en cualquier dirección (no en diagonal) hacia cualquier bloque siempre que el bloque no sea un callejón sin salida.
La tarea es comprobar si existe algún camino para que la rata pueda llegar a la comida o no. No es necesario imprimir la ruta.
Ejemplos :
Input : maze[4][5] = {
{1, 0, 1, 1, 0},
{1, 1, 1, 0, 1},
{0, 1, 0, 1, 1},
{1, 1, 1, 1, 1}
}
fx = 2, fy=3
Output : Path Found!
The path can be: (0, 0) -> (1, 0) -> (1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3) -> (2, 3)
Este es el famoso problema de la Rata en un Laberinto planteado en muchas entrevistas que se puede resolver usando Recursion y Backtracking. Ya hemos discutido una solución de Backtracking para este problema usando recursividad en Rat in a Maze | Retroceso-2 . En esto se discute una solución iterativa usando stack.
En el artículo anterior , Recursion usa una pila de llamadas para mantener en el almacén cada llamada recursiva y luego aparecer cuando finaliza la función. Eliminaremos la recursividad usando nuestra propia pila para hacer lo mismo.
Se utiliza una estructura de Node para almacenar las coordenadas (i, j) y las direcciones exploradas desde este Node y qué dirección probar a continuación.
Estructura utilizada:
- X : coordenada x del Node
- Y : coordenada y del Node
- dir : esta variable se usará para decir qué direcciones hemos probado y cuál elegir a continuación. Probaremos todas las direcciones en sentido contrario a las agujas del reloj empezando por Arriba. Inicialmente se le asignará 0.
- Si dir=0 prueba la dirección hacia arriba.
- Si dir=1 intente dirección izquierda.
- Si dir=2 prueba la dirección hacia abajo.
- Si dir=3 intente en la dirección correcta.
Inicialmente, empujaremos un Node con índices i=0, j=0 y dir=0 en la pila. Nos moveremos en todas las direcciones del Node superior uno por uno en sentido contrario a las agujas del reloj y cada vez que intentemos un nuevo camino empujaremos ese Node (bloque del laberinto) en la pila. Aumentaremos la variable dir del Node superior cada vez para que podamos probar una nueva dirección cada vez a menos que se exploren todas las direcciones, es decir. dirección=4. Si dir es igual a 4, sacaremos ese Node de la pila, lo que significa que estamos retrocediendo un paso hacia el camino de donde vinimos.
También mantendremos una array visitada que mantendrá qué bloques del laberinto ya se usan en el camino o, en otras palabras, están presentes en la pila. Mientras probamos cualquier dirección, también verificaremos si el bloque del laberinto no es un callejón sin salida y tampoco está fuera del laberinto.
Haremos esto mientras las coordenadas del Node superior se vuelven iguales a las coordenadas de la comida, lo que significa que hemos llegado a la comida o la pila se vacía, lo que significa que no hay un camino posible para llegar a la comida.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to solve Rat in a maze
// problem with backtracking using stack
#include <cstring>
#include <iostream>
#include <stack>
using namespace std;
#define N 4
#define M 5
class node {
public:
int x, y;
int dir;
node(int i, int j)
{
x = i;
y = j;
// Initially direction
// set to 0
dir = 0;
}
};
// maze of n*m matrix
int n = N, m = M;
// Coordinates of food
int fx, fy;
bool visited[N][M];
bool isReachable(int maze[N][M])
{
// Initially starting at (0, 0).
int i = 0, j = 0;
stack<node> s;
node temp(i, j);
s.push(temp);
while (!s.empty()) {
// Pop the top node and move to the
// left, right, top, down or retract
// back according the value of node's
// dir variable.
temp = s.top();
int d = temp.dir;
i = temp.x, j = temp.y;
// Increment the direction and
// push the node in the stack again.
temp.dir++;
s.pop();
s.push(temp);
// If we reach the Food coordinates
// return true
if (i == fx and j == fy) {
return true;
}
// Checking the Up direction.
if (d == 0) {
if (i - 1 >= 0 and maze[i - 1][j] and
visited[i - 1][j]) {
node temp1(i - 1, j);
visited[i - 1][j] = false;
s.push(temp1);
}
}
// Checking the left direction
else if (d == 1) {
if (j - 1 >= 0 and maze[i][j - 1] and
visited[i][j - 1]) {
node temp1(i, j - 1);
visited[i][j - 1] = false;
s.push(temp1);
}
}
// Checking the down direction
else if (d == 2) {
if (i + 1 < n and maze[i + 1][j] and
visited[i + 1][j]) {
node temp1(i + 1, j);
visited[i + 1][j] = false;
s.push(temp1);
}
}
// Checking the right direction
else if (d == 3) {
if (j + 1 < m and maze[i][j + 1] and
visited[i][j + 1]) {
node temp1(i, j + 1);
visited[i][j + 1] = false;
s.push(temp1);
}
}
// If none of the direction can take
// the rat to the Food, retract back
// to the path where the rat came from.
else {
visited[temp.x][temp.y] = true;
s.pop();
}
}
// If the stack is empty and
// no path is found return false.
return false;
}
// Driver code
int main()
{
// Initially setting the visited
// array to true (unvisited)
memset(visited, true, sizeof(visited));
// Maze matrix
int maze[N][M] = {
{ 1, 0, 1, 1, 0 },
{ 1, 1, 1, 0, 1 },
{ 0, 1, 0, 1, 1 },
{ 1, 1, 1, 1, 1 }
};
// Food coordinates
fx = 2;
fy = 3;
if (isReachable(maze)) {
cout << "Path Found!" << '\n';
}
else
cout << "No Path Found!" << '\n';
return 0;
}
Java
// Java program to solve Rat in a maze
// problem with backtracking using stack
import java.util.Stack;
class Node
{
private int x, y;
private int dir;
public Node(int i, int j)
{
this.x = i;
this.y = j;
// default value for direction set to 0 (Up)
this.dir = 0;
}
public int getX()
{
return x;
}
public void setX(int x)
{
this.x = x;
}
public int getY()
{
return y;
}
public void setY(int y)
{
this.y = y;
}
public int getDir()
{
return dir;
}
public void setDir(int dir)
{
this.dir = dir;
}
}
public class RatInMaze
{
private static final int N = 4;
private static final int M = 5;
// maze of n*m matrix
int n = N, m = M;
private static boolean[][] visited = new boolean[N][M];
// Driver code
public static void main(String[] args)
{
// Initially setting the visited
// array to true (unvisited)
setVisited(true);
// Maze matrix
int maze[][] = {{ 1, 0, 1, 1, 0 },
{ 1, 1, 1, 0, 1 },
{ 0, 1, 0, 1, 1 },
{ 1, 1, 1, 1, 1 } };
if (isReachable(maze))
{
System.out.println("Path Found!\n");
}
else
System.out.println("No Path Found!\n");
}
private static void setVisited(boolean b)
{
for (int i = 0; i < visited.length; i++)
{
for (int j = 0; j < visited[i].length; j++)
{
visited[i][j] = b;
}
}
}
private static boolean isReachable(int maze[][])
{
// Initially starting at (0, 0).
int i = 0, j = 0;
// Food coordinates
// Coordinates of food
int fx, fy;
fx = 2;
fy = 3;
Stack<Node> s = new Stack<Node>();
Node temp = new Node(i, j);
s.push(temp);
while (!s.empty())
{
// Pop the top node and move to the
// left, right, top, down or retract
// back according the value of node's
// dir variable.
temp = s.peek();
int d = temp.getDir();
i = temp.getX();
j = temp.getY();
// Increment the direction and
// push the node in the stack again.
temp.setDir(temp.getDir() + 1);
s.pop();
s.push(temp);
// If we reach the Food coordinates
// return true
if (i == fx && j == fy)
{
return true;
}
if (d == 0)
{
// Checking the Up direction.
if (i - 1 >= 0 && maze[i - 1][j] == 1 &&
visited[i - 1][j])
{
Node temp1 = new Node(i - 1, j);
visited[i - 1][j] = false;
s.push(temp1);
}
}
else if (d == 1)
{
// Checking the left direction
if (j - 1 >= 0 && maze[i][j - 1] == 1 &&
visited[i][j - 1])
{
Node temp1 = new Node(i, j - 1);
visited[i][j - 1] = false;
s.push(temp1);
}
}
else if (d == 2)
{
// Checking the down direction
if (i + 1 < N && maze[i + 1][j] == 1 &&
visited[i + 1][j])
{
Node temp1 = new Node(i + 1, j);
visited[i + 1][j] = false;
s.push(temp1);
}
}
else if (d == 3)
{
// Checking the right direction
if (j + 1 < M && maze[i][j + 1] == 1 &&
visited[i][j + 1])
{
Node temp1 = new Node(i, j + 1);
visited[i][j + 1] = false;
s.push(temp1);
}
}
// If none of the direction can take
// the rat to the Food, retract back
// to the path where the rat came from.
else
{
visited[temp.getX()][temp.getY()] = true;
s.pop();
}
}
// If the stack is empty and
// no path is found return false.
return false;
}
}
// This code is contributed by nirajtechi
C#
// C# program to solve Rat in a maze
// problem with backtracking using stack
using System;
using System.Collections.Generic;
public class Node
{
private int x, y;
private int dir;
public Node(int i, int j)
{
this.x = i;
this.y = j;
// default value for direction set to 0 (Up)
this.dir = 0;
}
public int getX()
{
return x;
}
public void setX(int x)
{
this.x = x;
}
public int getY()
{
return y;
}
public void setY(int y)
{
this.y = y;
}
public int getDir()
{
return dir;
}
public void setDir(int dir)
{
this.dir = dir;
}
}
public class RatInMaze
{
private static readonly int N = 4;
private static readonly int M = 5;
// maze of n*m matrix
int n = N, m = M;
private static bool [,]visited = new bool[N,M];
// Driver code
public static void Main(String[] args)
{
// Initially setting the visited
// array to true (unvisited)
setVisited(true);
// Maze matrix
int [,]maze = {{ 1, 0, 1, 1, 0 },
{ 1, 1, 1, 0, 1 },
{ 0, 1, 0, 1, 1 },
{ 1, 1, 1, 1, 1 } };
if (isReachable(maze))
{
Console.WriteLine("Path Found!\n");
}
else
Console.WriteLine("No Path Found!\n");
}
private static void setVisited(bool b)
{
for (int i = 0; i < visited.GetLength(0); i++)
{
for (int j = 0; j < visited.GetLength(0); j++)
{
visited[i,j] = b;
}
}
}
private static bool isReachable(int [,]maze)
{
// Initially starting at (0, 0).
int i = 0, j = 0;
// Food coordinates
// Coordinates of food
int fx, fy;
fx = 2;
fy = 3;
Stack<Node> s = new Stack<Node>();
Node temp = new Node(i, j);
s.Push(temp);
while (s.Count!=0)
{
// Pop the top node and move to the
// left, right, top, down or retract
// back according the value of node's
// dir variable.
temp = s.Peek();
int d = temp.getDir();
i = temp.getX();
j = temp.getY();
// Increment the direction and
// push the node in the stack again.
temp.setDir(temp.getDir() + 1);
s.Pop();
s.Push(temp);
// If we reach the Food coordinates
// return true
if (i == fx && j == fy)
{
return true;
}
if (d == 0)
{
// Checking the Up direction.
if (i - 1 >= 0 && maze[i - 1,j] == 1 &&
visited[i - 1,j])
{
Node temp1 = new Node(i - 1, j);
visited[i - 1,j] = false;
s.Push(temp1);
}
}
else if (d == 1)
{
// Checking the left direction
if (j - 1 >= 0 && maze[i,j - 1] == 1 &&
visited[i,j - 1])
{
Node temp1 = new Node(i, j - 1);
visited[i,j - 1] = false;
s.Push(temp1);
}
}
else if (d == 2)
{
// Checking the down direction
if (i + 1 < N && maze[i + 1,j] == 1 &&
visited[i + 1,j])
{
Node temp1 = new Node(i + 1, j);
visited[i + 1,j] = false;
s.Push(temp1);
}
}
else if (d == 3)
{
// Checking the right direction
if (j + 1 < M && maze[i,j + 1] == 1 &&
visited[i,j + 1])
{
Node temp1 = new Node(i, j + 1);
visited[i,j + 1] = false;
s.Push(temp1);
}
}
// If none of the direction can take
// the rat to the Food, retract back
// to the path where the rat came from.
else
{
visited[temp.getX(),temp.getY()] = true;
s.Pop();
}
}
// If the stack is empty and
// no path is found return false.
return false;
}
}
// This code contributed by Rajput-Ji
Python3
# Python3 program to solve Rat in a maze
# problem with backtracking using stack
N=4
M=5
class node:
def __init__(self,i,j):
self.x=i
self.y=j
self.dirn=0
# maze of n*m matrix
n = N; m = M
# Coordinates of food
fx=0; fy=0
visited=[[True]*N for _ in range(M)]
def isReachable(maze):
# Initially starting at (0, 0).
i = 0; j = 0
s=[]
temp=node(i, j)
s.append(temp)
while s:
# Pop the top node and move to the
# left, right, top, down or retract
# back according the value of node's
# dirn variable.
temp = s.pop()
d = temp.dirn
i = temp.x; j = temp.y
# Increment the direction and
# push the node in the stack again.
temp.dirn+=1
s.append(temp)
# If we reach the Food coordinates
# return true
if (i == fx and j == fy):
return True
# Checking the Up direction.
if (d == 0):
if (i - 1 >= 0 and maze[i - 1][j] and visited[i - 1][j]):
temp1=node(i - 1, j)
visited[i - 1][j] = False
s.append(temp1)
# Checking the left direction
elif (d == 1):
if(j - 1 >= 0 and maze[i][j - 1] and visited[i][j - 1]):
temp1=node(i, j - 1)
visited[i][j - 1] = False
s.append(temp1)
# Checking the down direction
elif (d == 2):
if(i + 1 < n and maze[i + 1][j] and visited[i + 1][j]):
temp1=node(i + 1, j)
visited[i + 1][j] = False
s.append(temp1)
# Checking the right direction
elif (d == 3):
if (j + 1 < m and maze[i][j + 1] and visited[i][j + 1]):
temp1=node(i, j + 1)
visited[i][j + 1] = False
s.append(temp1)
# If none of the direction can take
# the rat to the Food, retract back
# to the path where the rat came from.
else:
visited[temp.x][temp.y] = True
s.pop()
# If the stack is empty and
# no path is found return false.
return False
# Driver code
if __name__ == '__main__':
# Initially setting the visited
# array to true (unvisited)
# Maze matrix
maze = [
[ 1, 0, 1, 1, 0 ],
[ 1, 1, 1, 0, 1 ],
[ 0, 1, 0, 1, 1 ],
[ 1, 1, 1, 1, 1 ]
]
# Food coordinates
fx = 2
fy = 3
if (isReachable(maze)):
print("Path Found!")
else:
print("No Path Found!")
Javascript
<script>
// JavaScript program to solve Rat in a maze
// problem with backtracking using stack
const N = 4
const M = 5
class node{
constructor(i, j){
this.x = i
this.y = j
this.dirn = 0
}
}
// maze of n*m matrix
let n = N, m = M
// Coordinates of food
let fx = 0, fy = 0
let visited = new Array(N);
for(let i = 0; i < N; i++){
visited[i] = new Array(M).fill(true);
}
function isReachable(maze){
// Initially starting at (0, 0).
let i = 0, j = 0
let s=[]
let temp=new node(i, j)
s.push(temp)
while(s.length>0){
// Pop the top node && move to the
// left, right, top, down or retract
// back according the value of node's
// dirn variable.
temp = s[s.length - 1]
s.pop()
let d = temp.dirn
i = temp.x, j = temp.y
// Increment the direction &&
// push the node in the stack again.
temp.dirn+=1
s.push(temp)
// If we reach the Food coordinates
// return true
if (i == fx && j == fy)
return true
// Checking the Up direction.
if (d == 0){
if (i - 1 >= 0 && maze[i - 1][j] && visited[i - 1][j]){
let temp1=new node(i - 1, j)
visited[i - 1][j] = false
s.push(temp1)
}
}
// Checking the left direction
else if (d == 1){
if(j - 1 >= 0 && maze[i][j - 1] && visited[i][j - 1]){
let temp1=new node(i, j - 1)
visited[i][j - 1] = false
s.push(temp1)
}
}
// Checking the down direction
else if (d == 2){
if(i + 1 < n && maze[i + 1][j] && visited[i + 1][j]){
let temp1=new node(i + 1, j)
visited[i + 1][j] = false
s.push(temp1)
}
}
// Checking the right direction
else if (d == 3){
if (j + 1 < m && maze[i][j + 1] && visited[i][j + 1]){
let temp1=new node(i, j + 1)
visited[i][j + 1] = false
s.push(temp1)
}
}
// If none of the direction can take
// the rat to the Food, retract back
// to the path where the rat came from.
else{
visited[temp.x][temp.y] = true
s.pop()
}
}
// If the stack is empty &&
// no path is found return false.
return false
}
// Driver code
// Initially setting the visited
// array to true (unvisited)
// Maze matrix
let maze = [
[ 1, 0, 1, 1, 0 ],
[ 1, 1, 1, 0, 1 ],
[ 0, 1, 0, 1, 1 ],
[ 1, 1, 1, 1, 1 ]
]
// Food coordinates
fx = 2
fy = 3
if (isReachable(maze))
document.write("Path Found!","</br>")
else
document.write("No Path Found!","</br>")
// This code is contributed by shinjanpatra
</script>
Producción:
Path Found!
Nota: También podemos imprimir la ruta simplemente sacando los Nodes de las pilas y luego imprimiéndolos en orden inverso.
Complejidad de Tiempo : O( 
).
Espacio Auxiliar: O( 
).
Publicación traducida automáticamente
Artículo escrito por imdhruvgupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA