【每日算法】dfs解决迷宫问题

迷宫问题是比较基础的dfs类型算法题。主要是针对起点和终点来求解最小行走路径

这样的题目肯定是要有回溯过程，因为每一个节点，不是只走一个方向，是四个方向都要走到，才能够知道最终能否走到终点。这样的题目dfs基本框架就是：

int[][] directs = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

for (int i = 0; i < 4; i++) {
    int newX = firstPase[0] + directs[i][0];
    int newY = firstPase[1] + directs[i][1];

}

这样基本上就表达了我要走四个方向的想法。

接下来我们看每走一个节点，都需要做什么

1、当前节点合法吗？

2、当前节点能走吗（不能是墙）

符合这俩节点就大胆迈步。

if (newX >= 0 && newX < maze.length
        && newY >= 0 && newY < maze[0].length
        && !visited[newX][newY] && (maze[newX][newY] == 0|| maze[newX][newY]==3))

迈步之后我们还要做好两件事儿

第一件：记录好这一步当前迈出状态下，最小的步数

第二件：要撤回当前迈步，我应该如何撤回来

记录步数添加数组

Integer[][] steps

记录状态我们就添加数组

boolean[][] visited

如果迷宫数组是m*n，则我们也开m*n的数组记录当前位置是否已经被访问。

这样两件事就都完成了

粗略看下这个递归需要几个入参

1、maze迷宫数组

2、记录每个位置当前步数的数组steps

3、当前位置访问状态数组visited

最后还不要忘了一个参数，就是当前走到了那个位置x,y 也可以用数组将他俩放在一块。

看下代码实现
 

public void dfs(boolean[][] visited, int[][] maze, Integer[][] steps, int[] firstPase) {
        int x = firstPase[0];
        int y = firstPase[1];
        if (maze[x][y]==3) {
            minStep =Math.min(minStep,steps[x][y]);
            return ;
        }

        for (int i = 0; i < 4; i++) {
            int newX = firstPase[0] + directs[i][0];
            int newY = firstPase[1] + directs[i][1];
            if (newX >= 0 && newX < maze.length
                    && newY >= 0 && newY < maze[0].length
                    && !visited[newX][newY] && (maze[newX][newY] == 0|| maze[newX][newY]==3)) {
                visited[newX][newY]=true;
                steps[newX][newY] = Math.min(steps[newX][newY], steps[firstPase[0]][firstPase[1]] + 1);
                dfs(visited,maze,steps, new int[]{newX,newY});
                visited[newX][newY]=false;
            }
        }

    }

除了写好递归代码，还不要忘记初始化步骤的一些必须考虑

1、visited数组的初始化为false，表示每一个位置都可以访问。但是起点位置要设置为true，表示该位置已经被访问到

2、steps的初始化为Integer.MaX_VALUE这样就可以使用Math.min获取到最小值。

3、firstPase的初始化值为{0,0},如果是那种指定位置的迷宫，初始化要符合题目要求。

时间复杂度：O(m*n)

空间复杂度为：O(m*n)