LeetCode（动态规划）：980. 不同路径 III

关于 leetcode 980.不同路径III

将原本仅返回符合题意的路径数改为所有符合题意的具体路径

下面的code是将int 改为List<List<int[]>>

Code

这里没有写严谨的对数器去测试，但两种返回类型都是同一种思路，那我就不浪费时间了

// 整体思路和原本的题完全一样,仅仅只是因为在返回值上做一些改动而改动了一些细节

// 不同路径:原题输出结果为符合题意的路径数,将输出结果改为符合题意的具体路径
public class Solution {
    // ans 用来存储所有符合题意的路径
    static List<List<int[]>> ans = new ArrayList<>();
    // tmp 用来存储 row col 也就是符合题意的具体路径 int {row, col}
    static List<int[]> temp = new ArrayList<>();

    /**
     *
     * @param grid 二维网格
     * @return 返回值为 List<List<int[]>> 类型
     * 内层List对应的是temp存储具体的路径
     * 外层存所有符合题意的路径
     * 每个路径上的点都用 int[]{row, col} 存储
     */
    public static List<List<int[]>> uniquePathsIII(int[][] grid) {
        // 同样的初始化需要的参数
        int R = grid.length, L = grid[0].length, row = 0, col = 0, M = 0;
        for (int r = 0;r < R;r++) {
            for (int c = 0;c < L;c++) {
                if(grid[r][c] == 1) {
                    row = r; col = c; M++;
                } else if (grid[r][c] == 0) M++;
            }
        }
        // 这里设计的f函数就没有返回值了,但他是可以影响到全局的ans的
        f(grid,R,L,M,row,col);
        // 函数执行完了ans自然就存进了符合题意的所有路径
        return ans;
    }

    /**
     * 回溯
     * @param grid 二维网格
     * @param R 网格下边界
     * @param L 网格右边界
     * @param M 剩余格子可通过数
     * @param row 当前行
     * @param col 当前列
     */
    public static void f(int[][] grid, int R, int L, int M, int row, int col) {
        // 来到终点并且所有可通过的点都过了一遍就是符合题意的
        if (grid[row][col] == 2 && M == 0) {
            //
            temp.add(new int[]{row, col});
            // 这个时候就可以将这个符合题意的单条路径存入ans
            ans.add(new ArrayList<>(temp));
            temp.remove(temp.size()-1);
            return;
        }
        // 碰到障碍或单纯的来到终点都是不符合题意直接返回
        if (grid[row][col] == -1 || grid[row][col] == 2) return;
        // 拿零时变量记录当前点原本的值
        int tmp = grid[row][col];
        // 将当前点标记为以走过
        grid[row][col] = -1;
        // 将当前已走过的点存入temp这个还未成型的路径当中
        temp.add(new int[]{row, col});

        //-----------------------------------------

        // 下面的操作整体是由当前点出发决定上下左右四个方向上的移动
        // 如果当前位置不在上边界，就可以向上走
        if (row != 0) f(grid,R,L,M-1,row-1,col);
        // 如果当前位置不在下边界，就可以向下走
        if (row != R-1) f(grid,R,L,M-1,row+1,col);
        // 如果当前位置不在左边界，就可以向左走
        if (col != 0) f(grid,R,L,M-1,row,col-1);
        // 如果当前位置不在右边界，就可以向右走
        if (col != L-1) f(grid,R,L,M-1,row,col+1);

        //----------------------------------------------

        // 下面两个操作是为了不影响做下一次决定
        // 四个方向的决定做完返回到当前点,将当前点还原会做决定之前的值
        // 也就是之前记录在tmp里面的值
        grid[row][col] = tmp;
        // 将temp里最后一个点删除
        temp.remove(temp.size()-1);
    }

    // 文本表达
    public static String toString(List<int[]> path) {
        String p = "";
        for (int[] point : path) {
            p += "(" + point[0] + ", " + point[1] + ")" + " -> ";
        }
        return p + "end";
    }
    public static void main(String[] args) {
        // leetcode例子1
        int[][] grid1 = new int[][] {
                {1,0,0,0},
                {0,0,0,0},
                {0,0,2,-1}
        };

        // leetcode例子2
        int[][] grid2 = new int[][] {
                {1,0,0,0},
                {0,0,0,0},
                {0,0,0,2}
        };

        List<List<int[]>> allPath = uniquePathsIII(grid2);
        for (List<int[]> path : allPath) {
            System.out.println(toString(path));
        }
    }
}