Leetcode — 980. Unique Paths III (中文)

問題連結: https://leetcode.com/problems/unique-paths-iii/

在一個二維整數矩陣grid, 每個格子有可能為四種不同的形態:

• 1 代表這格是我們的起點位置, 整個矩陣中只會有一個起點
• 2 代表我們要走到的終點位置, 整個矩陣中只會有一個終點
• 0 代表我們可以走的格子
• -1 有障礙在這格上面, 我們不可穿越

當我們在各格子的時候, 我們的下一步可往上下左右任一格子走, 我們目標是從起點到終點, 走訪所有除了有放障礙物的格子, 且每個格子至多只能走過一次, 回傳這樣條件下, 可以安排的路線有幾個

範例
Input: [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 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)

想法:

如果你曾經在Leetcode上做過 62. Unique Paths 和 63. Unique Paths II, 你可以用動態規劃dynamic programming來解那兩題, 因為在62跟63題的時候, 有幾個規則讓我們可以利用先前找過的路線數加以利用

62和63題中, 我們只能往右或往下走, 且每次起點跟終點都是左上角跟右下角的位置, 因此從起點走到現在位置(i,j)的時候有幾條路線, 就是從起點走到現在位置的上格的路線 及 從起點走到現在位置的左格 的路線總和

然而, 你會發現這題跟62和63題完全不一樣, 現在每次的起點跟終點不但每次會改變, 且我們沒有被限制只能往右或往下走, 我們四個方位都可以走訪, 又加上我們又要提防重複走訪同一格的情況發生, 因此我們不能用動態規劃來幫我們簡化問題, 我們必須真的一次次走訪實際路線的每格, 來保證我們真的走訪每一格 且又沒有重複走到一樣的格子

因為我們每次都可以往上下左右走, 因此這四格都可能成為我們現在路線的下一步, 因此我們這四個格子都會試著走走看, 看我們是否能從現在這個路線中又變出新的不同路線們, 而是的, 這就是我們所謂的backtracking — 我們在座了一個決定後(決定下格位置), 我們會繼續做下一個決定找路, 直到我們沒路或直到我們走完整個路線後, 我們將會重做我們前一個做的決定, 再去試當我們走另一個格子的時候, 創造新路線可能性

程式邏輯:

在我們做任何決定前(也就是我們還沒進入"決定下一格要走哪"的循環), 我們需要先找到我們的起點到底在哪, 以及需要先數我們總共到底要走訪幾個格子

因為我們必須要知道我們到底走訪過那些格子, 我用一個list來記錄我們走訪過的格子, 若我們發現現在拜訪的位置不存在, 或者上面有障礙物, 或者在這個路線已走訪過, 那我們就會馬上重做我們剛剛的決定(因為我們剛剛在前一個位置選擇走這裡), 改選另一個格子, 我們會持續的幫這個路線一直去選下一個可能的格子直到我們幫這條路線找到終點或者發現這個路線是死路

以下為 20ms 的程式碼, 贏過 5% —

public int uniquePathsIII(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] start = new int[2];
        int count = 0;//number of 0s and starting point
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]==1)
                {
                    start[0] = i;
                    start[1] = j;
                }
                else if(grid[i][j]==0)
                    count++;
            }
        }
        return helper(grid, start[0],start[1], count+1, new ArrayList<>());
    }
    public int helper(int[][] grid,int i,int j, int count, List<String> visited){
        if(i<0||j<0||i>=grid.length||j>=grid[i].length||grid[i][j]==-1 ||visited.contains(i+" "+j))
            return 0;
        if(grid[i][j]==2)
        {
            if(visited.size()==count)
                return 1;
            return 0;
        }
        visited.add(i+" "+j);
        int rst = 0;
        rst += helper(grid, i+1, j, count, new ArrayList<>(visited));
        rst += helper(grid, i-1, j, count, new ArrayList<>(visited));
        rst += helper(grid, i, j+1, count, new ArrayList<>(visited));
        rst += helper(grid, i, j-1, count, new ArrayList<>(visited));
        return rst;
    }

而因為我們也沒有被禁止不能改一開始的二維矩陣中的值, 因此與其用list來記錄, 我們也可以好好利用二維矩陣來記錄我們走訪過的格子們

當我們在這個路線中拜訪某格子後, 我們可以放個石頭(也就是障礙物)在這個格子上, 這樣之後我在往後這個路線上拓展新路的時候就不會重複走訪同個格子了, 因此, 當我們在決定在這個路線上往下找下一個格子前, 我們會先在這個位置上放一顆石頭(gird[i][j]=1), 再往下走, 試完當我們往那四個格子後有沒有任何"希望"後, 我們再把石頭移開(gird[i][j]=0)

以下為 0ms 的程式碼, 贏過100% —

public int uniquePathsIII(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] start = new int[2];
        int count = 0;//number of 0s and starting point
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]==1)
                {
                    start[0] = i;
                    start[1] = j;
                }
                else if(grid[i][j]==0)
                    count++;
            }
        }
        return helper(grid, start[0],start[1], count+1);
    }
    public int helper(int[][] grid,int i,int j, int count){
        if(i<0||j<0||i>=grid.length||j>=grid[i].length||grid[i][j]==-1)
            return 0;
        if(grid[i][j]==2)
        {
            if(count==0)
                return 1;
            return 0;
        }
        grid[i][j] = -1;
        int rst = 0;
        rst += helper(grid, i+1, j, count-1);
        rst += helper(grid, i-1, j, count-1);
        rst += helper(grid, i, j+1, count-1);
        rst += helper(grid, i, j-1, count-1);
        grid[i][j] = 0;
        return rst;
    }