回溯算法解决迷宫问题java
时间: 2023-07-30 19:10:35 浏览: 37
回溯算法是一种经典的解决迷宫问题的方法。下面是一个Java实现的示例代码:
```java
public class MazeSolver {
private int[][] maze;
private int[][] solution;
private int mazeSize;
public MazeSolver(int[][] maze) {
this.maze = maze;
this.mazeSize = maze.length;
this.solution = new int[mazeSize][mazeSize];
}
public boolean solveMaze() {
if (solve(0, 0)) {
printSolution();
return true;
} else {
System.out.println("No feasible solution found...");
return false;
}
}
private boolean solve(int x, int y) {
if (isFinished(x, y)) {
return true;
}
if (isValidMove(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;
}
private boolean isValidMove(int x, int y) {
if (x < 0 || x >= mazeSize) {
return false;
}
if (y < 0 || y >= mazeSize) {
return false;
}
if (maze[x][y] == 0) {
return false;
}
if (solution[x][y] == 1) {
return false;
}
return true;
}
private boolean isFinished(int x, int y) {
if (x == mazeSize - 1 && y == mazeSize - 1) {
return true;
}
return false;
}
private void printSolution() {
for (int i = 0; i < mazeSize; i++) {
for (int j = 0; j < mazeSize; j++) {
System.out.print(solution[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
int[][] maze = {
{1, 1, 1, 0},
{1, 0, 1, 0},
{1, 1, 1, 0},
{0, 0, 1, 1}
};
MazeSolver solver = new MazeSolver(maze);
solver.solveMaze();
}
}
```
在此示例中,迷宫是一个二维数组,其中0表示墙壁,1表示可通过的路径。solveMaze()方法是入口点,它调用solve()方法来解决迷宫问题。isValidMove()方法检查当前位置是否是有效的移动位置。isFinished()方法检查当前位置是否已经到达终点。printSolution()方法打印出解决方案。