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

    1 表示起始方格。且只有一个起始方格。 2 表示结束方格，且只有一个结束方格。

    0 表示我们可以走过的空方格。

    -1 表示我们无法跨越的障碍。

    返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目，每一个无障碍方格都要通过一次。

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

    解题思路：深度优先遍历+回溯

    1. void back_trace(vector<vector<int>>& grid, int start_x, int start_y, 
    2.                    int non_obstacles, int & paths)
    3.     {
    4.         int m = grid.size();
    5.         int n = grid[0].size();
    6.         if(start_x<0 || start_x>=m ||       // 越界
    7.             start_y<0 || start_y>=n ||      // 越界
    8.             grid[start_x][start_y] == -1)   // 障碍
    9.             return;
    11.         if (grid[start_x][start_y] == 2)    // 到达终点
    12.         {
    13.             if (!non_obstacles)             // 走过了所有非障碍节点
    14.                 paths++;
    15.             return;
    16.         }
    18.         // 没有达到终点，也没有越界和遇到障碍
    19.         non_obstacles--;             // 需要走过的非障碍节点减少一个
    20.         grid[start_x][start_y] = -1; // 将当前节点设置成障碍，说明已经走过，设成不可通行
    22.         // 然后依次在四个方向去遍历
    23.         back_trace(grid, start_x+1, start_y, non_obstacles, paths);     // 上
    24.         back_trace(grid, start_x-1, start_y, non_obstacles, paths);     // 下
    25.         back_trace(grid, start_x, start_y-1, non_obstacles, paths);     // 左
    26.         back_trace(grid, start_x, start_y+1, non_obstacles, paths);     // 右
    28.         grid[start_x][start_y] = 0;  // 将当前点重新赋值回来，设成可通行
    30.     }
    31.     int uniquePathsIII(vector<vector<int>>& grid) {
    32.         int start_x, start_y;   // 找到起点位置
    33.         int non_obstacles = 0;  // 路径长度，等于0表示走过所有的非障碍点
    35.         int m = grid.size();
    36.         int n = grid[0].size();
    37.         for(int i=0; i<m; ++i){
    38.             for(int j=0; j<n; ++j){
    39.                 if (grid[i][j] == 1)
    40.                 {
    41.                     start_x = i;
    42.                     start_y = j;
    43.                 }
    44.                 else if(grid[i][j] != -1)
    45.                 {
    46.                     non_obstacles++;
    47.                 }
    48.             }
    49.         }
    51.         int paths = 0;  // paths
    52.         back_trace(grid, start_x, start_y, non_obstacles, paths);
    53.         return paths;
    54.     }

    欢迎交流，批评指正；如果觉得对你有用，赏杯水喝！
    image.pngWeChat Image_20200714101954.jpg