關(guān)于 leetcode 980.不同路徑III

將原本僅返回符合題意的路徑數(shù)改為所有符合題意的具體路徑

下面的code是將int 改為List<List<int[]>>

Code

這里沒有寫嚴謹?shù)膶?shù)器去測試，但兩種返回類型都是同一種思路，那我就不浪費時間了

// 整體思路和原本的題完全一樣,僅僅只是因為在返回值上做一些改動而改動了一些細節(jié)

// 不同路徑:原題輸出結(jié)果為符合題意的路徑數(shù),將輸出結(jié)果改為符合題意的具體路徑
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 二維網(wǎng)格
     * @return 返回值為 List<List<int[]>> 類型
     * 內(nèi)層List對應的是temp存儲具體的路徑
     * 外層存所有符合題意的路徑
     * 每個路徑上的點都用 int[]{row, col} 存儲
     */
    public static List<List<int[]>> uniquePathsIII(int[][] grid) {
        // 同樣的初始化需要的參數(shù)
        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函數(shù)就沒有返回值了,但他是可以影響到全局的ans的
        f(grid,R,L,M,row,col);
        // 函數(shù)執(zhí)行完了ans自然就存進了符合題意的所有路徑
        return ans;
    }

    /**
     * 回溯
     * @param grid 二維網(wǎng)格
     * @param R 網(wǎng)格下邊界
     * @param L 網(wǎng)格右邊界
     * @param M 剩余格子可通過數(shù)
     * @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});

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

        // 下面的操作整體是由當前點出發(fā)決定上下左右四個方向上的移動
        // 如果當前位置不在上邊界，就可以向上走
        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));
        }
    }
}