题解 | #迷宫问题#
第一次自己用dfs解决此类问题，成功！特此记录，主要有以下问题需要注意：
1.标志isGotPath用于找到完整路径之后要防止回溯删掉了ans里面的元素。当然，可以再另外定义一个List在路径完成时添加元素就不会被删掉，此种形式可以用于找到所有可能的路径。
2.访问过的位置需要置1，否则会栈溢出
import java.util.*;
public class Main {
static List<String> ans = new ArrayList<>(); // 存储标志
static boolean isGotPath = false; // 是否找到路径的标志
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] map = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
map[i][j] = sc.nextInt();
}
}
dfs(map, 0, 0);
for (String location : ans) {
System.out.println(location);
}
}
/**
一开始选择向右走，遇到走不通则向下走，如果向下也走不通则回溯
(x, y)表示当前位置坐标
*/
public static void dfs(int[][] map, int x, int y) {
if (isGotPath) {
return;
}
String location = "(" + x + "," + y + ")";
ans.add(location);
map[x][y] = 1; // 标记已经走过
if (x == map.length-1 && y == map[0].length-1) {
isGotPath = true;
return;
}
// 如果右边是可通过的，则进入
if (y < map[0].length-1 && map[x][y+1] == 0) {
dfs(map, x, y+1);
}
// 如果下边是可通过的，则进入
if (x < map.length-1 && map[x+1][y] == 0) {
dfs(map, x+1, y);
}
// 如果上边是可以通过，则进入
if (x > 0 && map[x-1][y] == 0) {
dfs(map, x-1, y);
}
// 如果左边可以通过，则进入
if (y > 0 && map[x][y-1] == 0) {
dfs(map, x, y-1);
}
if (isGotPath) return;
// 回溯
ans.remove(location);
map[x][y] = 0;
}
}
投递字节跳动等公司10个岗位