# 迷宫中的老鼠问题：使用回溯算法解决

## 本文概述

``Gray blocks are dead ends (value = 0).``

``````{1, 0, 0, 0}
{1, 1, 0, 1}
{0, 1, 0, 0}
{1, 1, 1, 1}``````

``````{1, 0, 0, 0}
{1, 1, 0, 0}
{0, 1, 0, 0}
{0, 1, 1, 1}
All enteries in solution path are marked as 1.``````

## 推荐：请在”实践首先, 在继续解决方案之前。

1. 创建一个初始为0的解决方案矩阵。
2. 创建一个递归函数, 该函数需要初始矩阵, 输出矩阵和rat(i, j)的位置。
3. 如果位置不在矩阵中或位置无效, 则返回。
4. 将位置输出[i] [j]标记为1, 然后检查当前位置是否为目的地。如果到达目的地, 则打印输出矩阵并返回。
5. 递归调用位置(i + 1, j)和(i, j + 1)。
6. 未标记位置(i, j), 即output [i] [j] = 0。

## C / C ++

``````/* C/C++ program to solve Rat in
a Maze problem using backtracking */
#include <stdio.h>

// Maze size
#define N 4

bool solveMazeUtil(
int maze[N][N], int x, int y, int sol[N][N]);

/* A utility function to print
solution matrix sol[N][N] */
void printSolution( int sol[N][N])
{
for ( int i = 0; i < N; i++) {
for ( int j = 0; j < N; j++)
printf ( " %d " , sol[i][j]);
printf ( "\n" );
}
}

/* A utility function to check if x, y is valid index for N*N maze */
bool isSafe( int maze[N][N], int x, int y)
{
// if (x, y outside maze) return false
if (
x >= 0 && x < N && y >= 0
&& y < N && maze[x][y] == 1)
return true ;

return false ;
}

/* 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.*/
bool solveMaze( int maze[N][N])
{
int sol[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } };

if (solveMazeUtil(
maze, 0, 0, sol)
== false ) {
printf ( "Solution doesn't exist" );
return false ;
}

printSolution(sol);
return true ;
}

/* A recursive utility function
to solve Maze problem */
bool solveMazeUtil(
int maze[N][N], int x, int y, int sol[N][N])
{
// if (x, y is goal) return true
if (
x == N - 1 && y == N - 1
&& maze[x][y] == 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)
== true )
return true ;

/* If moving in x direction
doesn't give solution then
Move down in y direction  */
if (solveMazeUtil(
maze, x, y + 1, sol)
== true )
return true ;

/* If none of the above movements
work then BACKTRACK: unmark
x, y as part of solution path */
sol[x][y] = 0;
return false ;
}

return false ;
}

// driver program to test above function
int main()
{
int maze[N][N] = { { 1, 0, 0, 0 }, { 1, 1, 0, 1 }, { 0, 1, 0, 0 }, { 1, 1, 1, 1 } };

solveMaze(maze);
return 0;
}``````

## Java

``````/* Java program to solve Rat in
a Maze problem using backtracking */

public class RatMaze {

// Size of the maze
static int N;

/* 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[][] = new int [N][N];

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
&& maze[x][y] == 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 } };

N = maze.length;
rat.solveMaze(maze);
}
}
// This code is contributed by Abhishek Shankhadhar``````

## Python3

``````# Python3 program to solve Rat in a Maze
# problem using backracking

# Maze size
N = 4

# A utility function to print solution matrix sol
def printSolution( sol ):

for i in sol:
for j in i:
print ( str (j) + " " , end = "")
print ("")

# A utility function to check if x, y is valid
# index for N * N Maze
def isSafe( maze, x, y ):

if x > = 0 and x < N and y > = 0 and y < N and maze[x][y] = = 1 :
return True

return False

""" 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 feasable solutions. """
def solveMaze( maze ):

# Creating a 4 * 4 2-D list
sol = [ [ 0 for j in range ( 4 ) ] for i in range ( 4 ) ]

if solveMazeUtil(maze, 0 , 0 , sol) = = False :
print ( "Solution doesn't exist" );
return False

printSolution(sol)
return True

# A recursive utility function to solve Maze problem
def solveMazeUtil(maze, x, y, sol):

# if (x, y is goal) return True
if x = = N - 1 and y = = N - 1 and maze[x][y] = = 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) = = True :
return True

# If moving in x direction doesn't give solution
# then Move down in y direction
if solveMazeUtil(maze, x, y + 1 , sol) = = True :
return True

# If none of the above movements work then
# BACKTRACK: unmark x, y as part of solution path
sol[x][y] = 0
return False

# Driver program to test above function
if __name__ = = "__main__" :
# Initialising the maze
maze = [ [ 1 , 0 , 0 , 0 ], [ 1 , 1 , 0 , 1 ], [ 0 , 1 , 0 , 0 ], [ 1 , 1 , 1 , 1 ] ]

solveMaze(maze)

# This code is contributed by Shiv Shankar``````

1值显示大鼠的路径

``````1  0  0  0
1  1  0  0
0  1  0  0
0  1  1  1``````

• 时间复杂度：O(2 ^(n ^ 2))。
递归可以运行上限2 ^(n ^ 2)次。
• 空间复杂度：O(n ^ 2)。
需要输出矩阵, 因此需要大小为n * n的额外空间。

• 回顶