题解 | #迷宫问题#
迷宫问题
https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc
本题是常规dfs和bfs常规应用题，要注意的是，需要输出路径的话，最好使用dfs，如果用bfs需要额外定义链表结构来辅助记录路径信息，如果要求最短路径的数量，用bfs最好
import java.io.IOException;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] maze = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
maze[i][j] = scanner.nextInt();
}
}
maze[0][0] = 1;
List<int[]> curPath = new ArrayList<>();
curPath.add(new int[]{0, 0});
dfs(maze, curPath, 0, 0);
for (int[] step : minPath) {
System.out.println("(" + step[0] + "," + step[1] + ")");
}
}
static List<int[]> minPath = null;
static int[][] steps = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
static void dfs(int[][] maze, List<int[]> curPath, int curI, int curJ) {
if (curI == maze.length - 1 && curJ == maze[0].length - 1) {
if (minPath == null || minPath.size() > curPath.size()) {
minPath = new ArrayList<>(curPath);
}
return;
}
for (int[] nextStep : steps) {
int nextI = curI + nextStep[0];
int nextJ = curJ + nextStep[1];
if (nextI >= 0 && nextJ >= 0
&& nextI < maze.length && nextJ < maze[0].length
&& maze[nextI][nextJ] != 1) {
maze[nextI][nextJ] = 1;
curPath.add(new int[]{nextI, nextJ});
dfs(maze, curPath, nextI, nextJ);
curPath.remove(curPath.size() - 1);
maze[nextI][nextJ] = 0;
}
}
}
}
