回溯算法之迷宫问题java
时间: 2023-10-14 21:09:13 浏览: 109
迷宫问题是指在一个矩阵中从起点开始,只能朝上、下、左、右四个方向移动,要求找到一条通向终点的路径。这个问题可以使用回溯算法来解决。
下面是一个Java的迷宫问题回溯算法实现,具体注释在代码中。
```java
import java.util.Scanner;
public class Maze {
private int[][] maze; // 迷宫矩阵
private int[][] solution; // 路径矩阵
private int N; // 迷宫大小
// 构造函数
public Maze(int n) {
N = n;
maze = new int[N][N];
solution = new int[N][N];
}
// 输入迷宫矩阵
public void inputMaze() {
System.out.println("请输入迷宫矩阵:");
Scanner scanner = new Scanner(System.in);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
maze[i][j] = scanner.nextInt();
}
}
}
// 输出迷宫矩阵
public void outputMaze() {
System.out.println("迷宫矩阵:");
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(maze[i][j] + " ");
}
System.out.println();
}
}
// 输出路径
public void outputSolution() {
System.out.println("路径:");
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(solution[i][j] + " ");
}
System.out.println();
}
}
// 判断当前位置是否可达
public boolean isSafe(int x, int y) {
// 判断是否越界
if (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1 && solution[x][y] == 0) {
return true;
}
return false;
}
// 回溯算法求解迷宫问题
public boolean solve(int x, int y) {
if (x == N - 1 && y == N - 1) { // 到达终点
solution[x][y] = 1;
return true;
}
if (isSafe(x, y)) { // 当前位置可达
solution[x][y] = 1; // 标记为已经走过
if (solve(x + 1, y)) { // 向下走
return true;
}
if (solve(x, y + 1)) { // 向右走
return true;
}
if (solve(x - 1, y)) { // 向上走
return true;
}
if (solve(x, y - 1)) { // 向左走
return true;
}
solution[x][y] = 0; // 四个方向都无法到达终点,回溯
return false;
}
return false;
}
public static void main(String[] args) {
Maze maze = new Maze(5); // 创建一个5x5的迷宫
maze.inputMaze(); // 输入迷宫矩阵
maze.outputMaze(); // 输出迷宫矩阵
if (maze.solve(0, 0)) { // 从起点开始求解迷宫问题
maze.outputSolution(); // 输出路径
} else {
System.out.println("无解!");
}
}
}
```
该算法的时间复杂度为$O(4^{n^2})$,因为对于每个位置都有四个方向可以选择,而迷宫的大小是$n \times n$。因此,该算法只适用于小规模的迷宫问题。
阅读全文