Java 中的老鼠迷宫问题

17 Mar 2025 | 5 分钟阅读

在本节中，我们将讨论 Java 中的老鼠进迷宫问题。老鼠进迷宫问题是面试中经常问到的一个著名的回溯问题。

问题描述：给定一个 R * C 矩阵作为迷宫，其中 R 是行数，C 是列数（R 可能等于 C，也可能不等于 C）。单元格 m[0][0] 是起点（参见下图）。老鼠从起点开始它的旅程。老鼠必须到达目的地单元格 m[R - 1][C - 1]。老鼠只能从当前所在的单元格向右（→）或向下（↓）移动。同时请注意，老鼠只能移动到相邻的单元格。例如，从单元格 m[0][0] 可以移动到 m[0][1] 或 m[1][0]。从 m[0][0] 不能直接移动到 m[0][2] 或 m[2][0]，因为单元格 m[0][2] 或 m[2][0] 与 m[0][0] 不是相邻的。

以下是上述迷宫的二进制表示。

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

其中，0 表示单元格是开放的，老鼠可以进入。1 表示单元格被阻止，老鼠不能进入。

下图显示了老鼠可以遵循的到达目的地的路径。

以下是上面所示路径的二进制表示。

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

只有标记为 0 的条目才表示路径。

方法

方法是创建一个递归函数。递归函数将从源单元格开始跟踪一条路径，并检查该路径是否到达了目标单元格。如果路径未能到达目标单元格，则回溯并尝试其他路径。

算法

基于上述方法，编写了以下算法。

创建一个结果矩阵（result[R][C]），并将矩阵的每个单元格填充为 1。
创建一个递归函数，该函数接收初始矩阵、结果矩阵以及老鼠的当前位置（初始为 (0, 0)）。
如果位置超出了矩阵范围，或者老鼠进入的位置无效，则返回。这是因为该路径不可能是正确的路径。因此，无需继续。
将单元格 result[r][c] 的值设置为 0，然后检查当前单元格是否是目标单元格。如果到达了目标单元格，则显示结果矩阵并终止。
如果未到达目标单元格，则递归地检查位置 (r + 1, c) 和 (r, c + 1)。
如果老鼠无法从位置 (r, c) 到达目标单元格，则取消标记该位置或单元格 (r, c)，即 result[r][c] = 1。

实施

让我们看看如何实现上述数学公式。观察以下示例。

文件名： RatMazeProblem.java

public class RatMazeProblem 
{

// Size of the maze
static int R;
static int C;

// A utility method to display
// the outcome matrix result[R][C] 
void displaySolution(int result[][])
{
System.out.println("The resultant matrix is: ");
for (int r = 0; r < R; r++) 
{
for (int c = 0; c < C; c++)
{
System.out.print(" " + result[r][c] + " ");
}

System.out.println();
}
}

// A utility method to validate
// whether r, c is the valid index for the R * C maze 
boolean isValid(int maze[][], int r, int c)
{
// if (r, c is outside the maze, then return false
return (r >= 0 && r < R && c >= 0 && c < C && maze[r][c] == 0);
}

// The method solves the rat maze problem with the
// help of Backtracking. It uses the solveMazeUtility()
// method to find the solution to the problem. The method returns false 
// when there is no single valid path from source to destination, otherwise true is 
// returned 

// and displays the path using 0s. Note that there can be more than one path
// from source to destination. However, the method displays one of the feasible ones. 
boolean findPathMaze(int maze[][])
{
int maz[][] = new int[R][C];
for(int r = 0; r < R; r++)
{
for(int c = 0; c < C; c++)
{
maz[r][c] = 1;
}
}


if (solveMazeUtility(maze, 0, 0, maz) == false) 
{
System.out.print("Path from source to destination doesn't exist");
return false;
}

displaySolution(maz);
return true;
}

// A recursive utility method to find the solution of the Maze
// problem 
boolean solveMazeUtility(int maze[][], int r, int c,
		int res[][])
{
// if r, c is the destination, then return true
if (r == R - 1 && c == C - 1 && maze[r][c] == 0) 
{
res[r][c] = 0;
return true;
}

// Check if the maze[r][c] is valid
if (isValid(maze, r, c) == true) 
{
// checking whether the current cell has been the part of the solution path or not
if (res[r][c] == 0)
{
return false;
}

// marking res(r, c) as the part of the solution path
res[r][c] = 0;

// Moving forward in the downward direction 
if (solveMazeUtility(maze, r + 1, c, res))
{
return true;
}
// If moving in downward direction does not provide
// the solution then we move in the rightward direction
if (solveMazeUtility(maze, r, c + 1, res))
{
return true;
}
// If moving in the downward direction does not provide
// the solution then start moving upward 
if (solveMazeUtility(maze, r - 1, c, res))
{
return true;
}
// If moving in the rigtward direction does not provide
// solution then start moving in the left 
if (solveMazeUtility(maze, r, c - 1, res))
{
return true;
}
// if a valid path is not possible from
// the cell (r, c), then mark it as 1
res[r][c] = 1;
return false;
}
return false;
}
// main method
public static void main(String argvs[])
{
// creating an object of the class RatMazeProblem
RatMazeProblem r = new RatMazeProblem();
// creating the maze
int maze[][] = { { 0, 1, 1, 1 },
		       { 0, 0, 1, 0 },
		       { 1, 0, 1, 1 },
		       { 0, 0, 0, 0 } };

R = maze.length;
C = maze[0].length;
r.findPathMaze(maze);
}
}

输出

The resultant matrix is: 
 0  1  1  1 
 0  0  1  1 
 1  0  1  1 
 1  0  0  0

时间复杂度：上述示例中提到的递归最多可以运行 2^(n^2) 次。因此，该程序的 time complexity 为 O(2 ^ (n ^ 2))。

空间复杂度：由于我们使用了额外的矩阵（maz[][]）。因此，该程序的 space complexity 为 O(n ^ 2)。

下一个主题Java 中的数独

Java 中的老鼠迷宫问题

方法

算法

实施

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中的老鼠迷宫问题

方法

算法

实施

相关帖子

Java 中的有效数字问题

Java 登录尝试计数

Java 中的 ArithmeticException

MetaClass in Java

SimpleTimeZone setRawOffset() method in Java with Examples

Java 的 Kalangs 是谁

如何在 Java 中从当前日期计算周数

Validate an IP Address in Java

Java 中的 extends vs. implements

Java 游戏

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器