java dfs 深层次理解 | #迷宫问题#

对遍历过的位置记录的几种写法：

一种是进入函数前标记访问，出函数标记未访问

另一种就是下述代码：确定符合要求再更改visited

优化点：

在进入findPath函数钱首先判断更改的坐标是否越界（比如x-1后是否为负数）

对于是否有通路喝是否访问过放在函数体内减少代码量

if(isWall[x][y] || visited[x][y]) return false;

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static int row;
    static int col;
    static ArrayList<Integer[]> path = new ArrayList<>();
    static boolean[][] visited;
    static boolean[][] isWall;

    public static boolean findPath(int x, int y){
        if(isWall[x][y] || visited[x][y]) return false;

        visited[x][y] = true;
        path.add(new Integer[]{x,y});

        if(x==row-1 && y==col-1)  return true;

        if(x-1>=0 && findPath(x-1,y))
            return true;
        if(x+1<isWall.length && findPath(x+1,y))
            return true;
        if(y-1>=0 && findPath(x,y-1))
            return true;
        if(y+1<isWall[0].length && findPath(x,y+1))
            return true;

        path.remove(path.size()-1);
        visited[x][y] = false;
        return false;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        row = in.nextInt();
        col = in.nextInt();
        isWall = new boolean[row][col];
        visited = new boolean[row][col];

        for(int i=0;i<row;i++)
            for(int j=0;j<col;j++)
                isWall[i][j] = in.nextInt()==1;

        findPath(0,0);
        for(Integer[] p : path)
            System.out.printf("(%d,%d)\n",p[0],p[1]);

    }
}