[leetcode] UniquePathsI, II, III

UniquePaths

• 問題描述：給定一個起點和終點，找到一共有多少條滿足條件的路徑。

Unique Paths I

• 給定一個矩陣，起點在左上角，終點在右下角。隻能向下走或者向右走。
• 思路：我們當然可以用DFS來做，但是時間複雜度就是 O ( 2 ( M ∗ N ) ) O(2^{(M*N)}) O(2(M∗N))。是以我們采用動态規劃的方法來做。
  • 轉移方程如下: d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ i ] [ j − 1 ] dp[i][j] = dp[i-1][j] + dp[i][j-1] dp[i][j]=dp[i−1][j]+dp[i][j−1]。
  • 初始化： d p [ 0 : i ] [ 0 ] = 1 , d p [ 0 ] [ 0 : j ] = 1 dp[0:i][0] = 1, dp[0][0:j] = 1 dp[0:i][0]=1,dp[0][0:j]=1
• 代碼：

int uniquePaths(int m, int n) {
        int res = 0;
//        bool visits[m * n];
//        memset(visits, false, sizeof(visits));
//        uniquePathsRecursive(m, n, 0, 0, visits, res);
        int dp[m][n];
        for(int i=0;i<m;i++){
            dp[i][0] = 1;
        }
        for(int j=0;j<n;j++){
            dp[0][j] = 1;
        }
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i == 0 || j == 0)
                    continue;
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        res = dp[m-1][n-1];
        return res;
    }
           

Unique Paths II

• 給定一個矩陣，起點在左上方，終點在右下方，路徑上還有一些點不能走，用1表示。隻能走下或右。計算有多少不同的路徑。
• 思路：還是動态規劃的想法，相比于I，我們更改一個條件：如果目前位置不可走，則dp[i][j] =0;
  • 轉移方程如下: d p [ i ] [ j ] = ( d p [ i − 1 ] [ j ] + d p [ i ] [ j − 1 ] ) ∗ ( g r i d [ i ] [ j ] = = 0 ) dp[i][j] = (dp[i-1][j] + dp[i][j-1]) * (grid[i][j] == 0) dp[i][j]=(dp[i−1][j]+dp[i][j−1])∗(grid[i][j]==0)。
  • 初始化
    • dp[0][0] = grid[0][0] == 0;
    • dp[i][0] = dp[i-1][0] && grid[i][0] == 0
    • dp[0][j] = dp[0][j-1] && grid[0][j] == 0
• 代碼：

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = (int) obstacleGrid.size();
        if(m == 0)
            return 0;
        int n = (int) obstacleGrid[0].size();
        //cout<<m<<", "<<n<<endl;
        long long dp[m][n];
        memset(dp, 0, sizeof(dp));
        if(obstacleGrid[0][0] != 0)
            return 0;
        dp[0][0] = 1;
        for(int i=1;i<m;i++){
            if(obstacleGrid[i][0] == 0 && dp[i-1][0] == 1){
                dp[i][0] = 1;
            }else{
                dp[i][0] = 0;
            }
        }
        for(int j=1;j<n;j++){
            if(obstacleGrid[0][j] == 0 && dp[0][j-1] == 1){
                dp[0][j] = 1;
            }else{
                dp[0][j] = 0;
            }
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(obstacleGrid[i][j] == 0)
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                else
                    dp[i][j] = 0;
            }
        }
        return dp[m-1][n-1];
    }
           

Unique Paths III

• 給定一個矩陣，0表示可以走，1表示起點，2表示終點，-1表示障礙物。此時可以向四個方向走。問從起點到終點，将所有可以路過的點路過有且隻有一次的走法有多少種。
• 思路
  • DFS是一種，我們首先計算出完整的路徑我們一共要走的步數，以及起始點和終點的坐标。然後我們有以下終止條件：
    • 如果步數達标
      • 目前點是終點，res += 1
      • 否則，return
    • 如果目前點是終點，步數沒達标
      • return
  • 動态規劃也是一種思路。
  • 整體來說動态規劃的思路和DFS比較相似。在leetcode上兩者的耗時也基本一緻。如下圖所示。

    

• 代碼：

class Solution {
public:
    bool isVaild(int x, int y, int m, int n){
        if(x>=0 && x<m && y>=0 && y<n){
            return true;
        }
        return false;
    }
    int dxs[4] = {1, 0, -1, 0};
    int dys[4] = {0, 1, 0, -1};
    void uniquePathsIIIRecursive(const vector<vector<int>>& grid, int m, int n, int x, int y, int step,
            int total_step, bool* visits, int& res){
        // cout<<x<<", "<<y<<endl;
        if(step == total_step){
            if(grid[x][y] == 2)
                res += 1;
            return;
        }
        if(grid[x][y] == 2){
            return;
        }
        for(int dir_id=0;dir_id<4;dir_id++){
            int new_x = x + dxs[dir_id];
            int new_y = y + dys[dir_id];
            if(isVaild(new_x, new_y, m, n)){
                int visit_pos = new_x * n + new_y;
                if(!visits[visit_pos] && grid[new_x][new_y] != -1){
                    visits[visit_pos] = true;
                    uniquePathsIIIRecursive(grid, m, n, new_x, new_y, step + 1, total_step, visits, res);
                    visits[visit_pos] = false;
                }
            }
        }
    }
    int uniquePathsIII(vector<vector<int>>& grid) {
        int m = (int) grid.size();
        if(m == 0){
            return 0;
        }
        int n = (int) grid[0].size();
        bool visits[m * n];
        memset(visits, false, sizeof(visits));
        int total_step = 0;
        int start_x = 0;
        int start_y = 0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j] == 0 || grid[i][j] == 2){
                    total_step += 1;
                }
                if(grid[i][j] == 1){
                    start_x = i;
                    start_y = j;
                }
            }
        }
        int res = 0;
        visits[start_x * n + start_y] = true;
        uniquePathsIIIRecursive(grid, m, n, start_x, start_y, 0, total_step, visits, res);
        return res;
    }
    int code(int x, int y, int m, int n){
        return 1 << (x * n + y);
    }
    int uniquePathsIII_V2(vector<vector<int>>& grid) {
        int m = (int) grid.size();
        if(m == 0){
            return 0;
        }
        int n = (int) grid[0].size();
        int start_x;
        int start_y;
        int target_x;
        int target_y;
        int target = 0;
        for(int i=0;i<m;i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    target |= code(i, j, m, n);
                } else {
                    if (grid[i][j] == 1) {
                        start_x = i;
                        start_y = j;
                    } else {
                        if (grid[i][j] == 2) {
                            target |= code(i, j, m, n);
                            target_x = i;
                            target_y = j;
                        }
                    }
                }
            }
        }
        return dp(start_x, start_y, m, n, target_x, target_y, target);
    }
    int dp(int x, int y, int m, int n, int target_x, int target_y, int to_do){
        if(to_do == 0){
            if(x == target_x && y == target_y)
                return 1;
            return 0;
        }
        if(x == target_x && y == target_y)
            return 0;
        int ans = 0;
        for(int i=0;i<4;i++){
            int new_x = x + dxs[i];
            int new_y = y + dys[i];
            if(isVaild(new_x, new_y, m, n)){
                if(to_do & code(new_x, new_y, m, n))
                    ans += dp(new_x, new_y, m, n, target_x, target_y, to_do ^ code(new_x, new_y, m, n));
            }
        }
        return ans;
    }
};