java dfs 输出路径
时间: 2023-05-15 17:06:59 浏览: 100
可以使用以下代码实现 Java 中的 DFS 输出路径:
```java
import java.util.*;
public class Main {
static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个方向
static int n, m;
static int[][] matrix;
static boolean[][] visited;
static List<int[]> path = new ArrayList<>(); // 存储路径
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
matrix = new int[n][m];
visited = new boolean[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
matrix[i][j] = sc.nextInt();
}
}
dfs(0, 0);
}
public static void dfs(int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= m || visited[x][y] || matrix[x][y] == 0) {
return;
}
visited[x][y] = true;
path.add(new int[]{x, y}); // 添加当前节点到路径中
if (x == n - 1 && y == m - 1) { // 到达终点,输出路径
for (int[] p : path) {
System.out.print("(" + p[0] + "," + p[1] + ") ");
}
System.out.println();
}
for (int[] dir : dirs) {
int nx = x + dir[0];
int ny = y + dir[1];
dfs(nx, ny);
}
path.remove(path.size() - 1); // 回溯,从路径中删除当前节点
visited[x][y] = false;
}
}
```
这段代码实现了一个简单的 DFS,用于输出从左上角到右下角的路径。其中 `matrix` 数组表示迷宫,0 表示障碍物,1 表示可以通过的路。`visited` 数组用于记录节点是否被访问过,`path` 列表用于存储路径。在 DFS 中,如果当前节点是终点,则输出路径;否则,遍历当前节点的四个方向,递归调用 DFS。在回溯时,从路径中删除当前节点,将当前节点标记为未访问。
阅读全文