题目

image.png

思路

  • 思路一：暴力递归+回溯，由于要求每条路径不能重复，因此我们可以通过回溯避免重复，又因为有四个方向，所以需要递归四个方向，递归结束条件：要求所有为0的都要走过一次，所以我们可以记录0的个数，然后每走一个就减去一个0个数，当个数为0时并且上下左右其中的一个就是终点，递归结束

    代码

    1.    //1.暴力递归+回溯
    2.   public int uniquePathsIII(int[][] grid) {
    3.       int target = 0, startI = 0, startJ = 0;
    4.       for (int i = 0; i < grid.length; i++) {
    5.           for (int j = 0; j < grid[0].length; j++) {
    6.               if (grid[i][j] == 0) target++;
    7.               if (grid[i][j] == 2) {
    8.                   startI = i;
    9.                   startJ = j;
    10.               }
    11.           }
    12.       }
    13.       //避免[1,2]或[2,1]情况
    14.       if (target == 0 && (startI - 1 >= 0
    15.            && grid[startI - 1][startJ] == 1 || startJ - 1 >= 0 
    16.            && grid[startI][startJ - 1] == 1 || startI + 1 < grid.length
    17.            && grid[startI + 1][startJ] == 1 || startJ + 1 < grid[0].length
    18.            && grid[startI][startJ + 1] == 1)) return 1;
    19.       return recur(grid, startI + 1, startJ , target)
    20.               + recur(grid, startI, startJ + 1, target)
    21.               + recur(grid, startI - 1, startJ, target)
    22.               + recur(grid, startI, startJ - 1, target);
    23.   }
    25.   public int recur(int[][] grid, int i, int j, int target) {
    26.       if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length|| grid[i][j] != 0) 
    27.           return 0;
    28.       target -= 1;
    29.       if (target == 0 && (i - 1 >= 0
    30.            && grid[i - 1][j] == 1 || j - 1 >= 0 
    31.            && grid[i][j - 1] == 1 || i + 1 < grid.length
    32.            && grid[i + 1][j] == 1 || j + 1 < grid[0].length
    33.            && grid[i][j + 1] == 1)) 
    34.            return 1;
    35.       grid[i][j] = 3;
    36.       int res = recur(grid, i + 1, j , target)
    37.               + recur(grid, i, j + 1, target)
    38.               + recur(grid, i - 1, j, target)
    39.               + recur(grid, i, j - 1, target);
    40.       grid[i][j] = 0;
    41.       return res;
    42.   }

    不同路径