Hemos discutido el problema de Backtracking y Knight’s tour en el Set 1 . Analicemos Rat in a Maze como otro problema de ejemplo que se puede resolver usando Backtracking.
Un laberinto se da como una array binaria N*N de bloques donde el bloque de origen es el bloque superior izquierdo, es decir, laberinto[0][0], y el bloque de destino es el bloque inferior derecho, es decir, laberinto[N-1][N-1 ]. Una rata parte de la fuente y tiene que llegar a su destino. La rata solo puede moverse en dos direcciones: hacia adelante y hacia abajo.
En la array del 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. Tenga en cuenta que esta es una versión simple del problema típico de Maze. Por ejemplo, una versión más compleja puede ser que la rata pueda moverse en 4 direcciones y una versión más compleja puede ser con un número limitado de movimientos.
El siguiente es un ejemplo de laberinto.
Gray blocks are dead ends (value = 0).
La siguiente es una representación de array binaria del laberinto anterior.
{1, 0, 0, 0}
{1, 1, 0, 1}
{0, 1, 0, 0}
{1, 1, 1, 1}
A continuación se muestra un laberinto con la ruta de solución resaltada.
A continuación se muestra la array de solución (salida del programa) para la array de entrada anterior.
{1, 0, 0, 0}
{1, 1, 0, 0}
{0, 1, 0, 0}
{0, 1, 1, 1}
All entries in solution path are marked as 1.
Java
/* Java program to solve Rat in a Maze problem using
backtracking */
public class RatMaze {
final int N = 4;
/* A utility function to print solution matrix
sol[N][N] */
void printSolution(int sol[][])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
System.out.print(" " + sol[i][j] + " ");
System.out.println();
}
}
/* A utility function to check if x, y is valid
index for N*N maze */
boolean isSafe(int maze[][], int x, int y)
{
// if (x, y outside maze) return false
return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1);
}
/* This function solves the Maze problem using
Backtracking. It mainly uses solveMazeUtil()
to solve the problem. It returns false if no
path is possible, otherwise return true and
prints the path in the form of 1s. Please note
that there may be more than one solutions, this
function prints one of the feasible solutions.*/
boolean solveMaze(int maze[][])
{
int sol[][] = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 } };
if (solveMazeUtil(maze, 0, 0, sol) == false) {
System.out.print("Solution doesn't exist");
return false;
}
printSolution(sol);
return true;
}
/* A recursive utility function to solve Maze
problem */
boolean solveMazeUtil(int maze[][], int x, int y,
int sol[][])
{
// if (x, y is goal) return true
if (x == N - 1 && y == N - 1) {
sol[x][y] = 1;
return true;
}
// Check if maze[x][y] is valid
if (isSafe(maze, x, y) == true) {
// mark x, y as part of solution path
sol[x][y] = 1;
/* Move forward in x direction */
if (solveMazeUtil(maze, x + 1, y, sol))
return true;
/* If moving in x direction doesn't give
solution then Move down in y direction */
if (solveMazeUtil(maze, x, y + 1, sol))
return true;
/* If none of the above movements works then
BACKTRACK: unmark x, y as part of solution
path */
sol[x][y] = 0;
return false;
}
return false;
}
public static void main(String args[])
{
RatMaze rat = new RatMaze();
int maze[][] = { { 1, 0, 0, 0 },
{ 1, 1, 0, 1 },
{ 0, 1, 0, 0 },
{ 1, 1, 1, 1 } };
rat.solveMaze(maze);
}
}
// This code is contributed by Abhishek Shankhadhar
1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 1
Complejidad del tiempo: O(2^(n^2))
Espacio auxiliar: O(n^2)
Consulte el artículo completo sobre Rata en un laberinto | Backtracking-2 para más detalles!
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