迷宫问题java dfs
时间: 2023-10-14 22:04:54 浏览: 48
好的,下面是一个使用深度优先搜索(DFS)解决迷宫问题的Java代码示例:
```java
import java.util.Stack;
public class MazeSolver {
private int[][] maze;
private boolean[][] visited;
private int startRow, startCol;
private int endRow, endCol;
public MazeSolver(int[][] maze, int startRow, int startCol, int endRow, int endCol) {
this.maze = maze;
this.visited = new boolean[maze.length][maze[0].length];
this.startRow = startRow;
this.startCol = startCol;
this.endRow = endRow;
this.endCol = endCol;
}
public boolean solve() {
Stack<Integer> stack = new Stack<>();
stack.push(startRow);
stack.push(startCol);
while (!stack.isEmpty()) {
int col = stack.pop();
int row = stack.pop();
if (row < 0 || col < 0 || row >= maze.length || col >= maze[0].length) {
continue;
}
if (visited[row][col] || maze[row][col] == 1) {
continue;
}
visited[row][col] = true;
if (row == endRow && col == endCol) {
return true;
}
stack.push(row + 1);
stack.push(col);
stack.push(row - 1);
stack.push(col);
stack.push(row);
stack.push(col + 1);
stack.push(row);
stack.push(col - 1);
}
return false;
}
public static void main(String[] args) {
int[][] maze = {
{0, 1, 0, 0},
{0, 1, 0, 1},
{0, 0, 0, 0},
{0, 1, 1, 0}
};
MazeSolver solver = new MazeSolver(maze, 0, 0, 3, 3);
if (solver.solve()) {
System.out.println("Maze solved!");
} else {
System.out.println("Maze cannot be solved!");
}
}
}
```
这个示例中,我们使用了一个栈来实现DFS算法,每次从栈中弹出一个坐标,然后检查是否越界、已经访问过或者是墙壁,如果是,则忽略这个坐标,否则标记为已访问并将其四周的坐标入栈。如果最终栈为空,则说明无法从起点到达终点,否则,说明找到了一条能够从起点到达终点的路径。
这只是一个简单的示例,实际上,如果要解决更复杂的迷宫问题,需要使用更高级的算法来优化搜索过程。