深度优先搜索

DFS

广度优先搜索一层一层遍历，每一层得到的所有新节点，要用队列存储起来以备下一层遍历的时候再遍历。

而深度优先搜索在得到一个新节点时立即对新节点进行遍历：从节点 0 出发开始遍历，得到到新节点 6 时，立马对新节点 6 进行遍历，得到新节点 4；如此反复以这种方式遍历新节点，直到没有新节点了，此时返回。返回到根节点 0 的情况是，继续对根节点 0 进行遍历，得到新节点 2，然后继续以上步骤。

从一个节点出发，使用 DFS 对一个图进行遍历时，能够遍历到的节点都是从初始节点可达的，DFS 常用来求解这种 可达性 问题。

在程序实现 DFS 时需要考虑以下问题：

• 栈：用栈来保存当前节点信息，当遍历新节点返回时能够继续遍历当前节点。可以使用递归栈。
• 标记：和 BFS 一样同样需要对已经遍历过的节点进行标记。

迷宫问题

题目描述：有一个 n * m 的迷宫，求从迷宫左上角到右下角的路径数量。

1 1 1 1
1 0 0 1
1 0 1 1
1 1 1 1

1表示可以通过，0表示障碍物，求解从（0，0）到（x，y）的方案有多少。

解决

枚举可以到达的路径（按照上右下左的方向）

1. [0,0]->[0,1]->[0,2]->[0,3]->[1,3]->[2,3]->[3,3] -end
2. [0,0]->[0,1]->[0,2]->[0,3]->[1,3]->[2,3]->[2,2]->[3,2]->[3,3] -end
3. [0,0]->[1,0]->[2,0]->[3,0]->[3,1]->[3,2]->[2,2]->[2,3]->[3,3] -end
4. [0,0]->[1,0]->[2,0]->[3,0]->[3,1]->[3,2]->[3,3] -end

public class DFSTest {

    //迷宫地图的二维数组
    static int[][] map = {{1, 1, 1, 1}, {1, 0, 0, 1}, {1, 0, 1, 1}, {1, 1, 1, 1}};
    //记录当前位置有没有被访问过
    static int[][] temp = new int[100][100];
    //按照上右下左的方向遍历迷宫
    static int[][] direction = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    //路径数量，初始值为0
    static int total = 0;

    public static void dfs(int[][] map, int x, int y) {
        int m = map.length;
        int n = map[0].length;
        //判断是否到达终点，并return
        if (x == m - 1 && y == n - 1) {
            total++;
            return;
        } else {
            for (int[] d : direction) {
                int nx = x + d[0];
                int ny = y + d[1];
                //判断坐标是否越界
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
                    continue;
                }
                if (temp[nx][ny] == 0 && map[nx][ny] == 1) {
                    //当前位置标记为访问过
                    temp[x][y] = 1;
                    //递归进行dfs
                    dfs(map, nx, ny);
                    //标记还原
                    temp[x][y] = 0;
                }
            }
        }
    }

    public static void main(String[] args) {
        dfs(map, 0, 0);
        System.out.println(total);
    }

}