深度优先搜索算法（DFS）原理及示例详解

1 算法原理

事实上，深度优先搜索属于图算法的一种，英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次.

举例说明之：下图是一个无向图，如果我们从A点发起深度优先搜索（以下的访问次序并不是唯一的，第二个点既可以是B也可以是C,D），则我们可能得到如下的一个访问过程：A->B->E（没有路了！回溯到A)->C->F->H->G->D（没有路，最终回溯到A,A也没有未访问的相邻节点，本次搜索结束）。

2 基本思路

深度优先遍历图的方法是，从图中某顶点v出发：

• （1）访问顶点v；
• （2）依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
• （3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。　当然，当人们刚刚掌握深度优先搜索的时候常常用它来走迷宫.事实上我们还有别的方法，那就是广度优先搜索(BFS).

搜索算法简而言之就是穷举所有可能情况并找到合适的答案，所以最基本的问题就是罗列出所有可能的情况。

从根开始计算，到找到位于某个节点的解，回溯法（深度优先搜索）作为最基本的搜索算法，其采用了一种“一只向下走，走不通就掉头”的思想（体会“回溯”二字），相当于采用了先根遍历的方法来构造搜索树。

980.不同路径

题目描述

在二维网格 grid 上，有 4 种类型的方格：

• 1 表示起始方格。且只有一个起始方格。
• 2 表示结束方格，且只有一个结束方格。
• 0 表示我们可以走过的空方格。
• -1 表示我们无法跨越的障碍。

返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。

每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。

输入输出示例

输入：
[1,0,0,0],
[0,0,0,0],
[0,0,2,-1]
输出： 2
**解释：**我们有以下两条路径：
(0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
(0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

直观思路

从起始点开始，朝着起始点的四个方向开始搜索，直到终点停止。

在搜索过程中，需要改变搜索方向，就如同逆时针输出二维数组的元素一样，当到达边界时需要改变方向。在此题中，定义两个方向，一个是改变row方向数组dr = {0, -1, 0, 1}，一个是column方向dc = {1, 0, -1, 0}。

代码实现

class Solution980 {
    int ans;
    int[][] grid;
    int tr, tc;
    int[] dr = new int[]{0, -1, 0, 1};
    int[] dc = new int[]{1, 0, -1, 0};
    int R, C;

    public int uniquePathsIII(int[][] grid) {
        this.grid = grid;
        R = grid.length;
        C = grid[0].length;

        int todo = 0;
        int sr = 0, sc = 0;
        for (int r = 0; r < R; ++r) {

        }
       ans = 0;
        dfs(sr, sc, todo);
        return ans;
    }

    public void dfs(int r, int c, int todo) {
        todo--;
        if (todo < 0) return;
        if (r == tr && c == tc) {
            if (todo == 0) ans++;
            return;
        }

        grid[r][c] = 3;
        for (int k = 0; k < 4; ++k) {
            int nr = r + dr[k];
            int nc = c + dc[k];
            if (0 <= nr && nr < R && 0 <= nc && nc < C) {
                if (grid[nr][nc] % 2 == 0)
                    dfs(nr, nc, todo);
            }
        }
        grid[r][c] = 0;
    }
}