【leetcode】Unique Paths II

Unique Paths II

Total Accepted: 22828 Total Submissions: 81414My Submissions

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

Note: m and n will be at most 100.

把存在Obstacle的位置标记为-1，表示无法通行

 class Solution {
 public:
     int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
         int m=obstacleGrid.size();
         int n=obstacleGrid[].size();

         int dp[][];

         dp[][]=obstacleGrid[][]==?-:;

         for(int i=;i<m;i++)
         {
             if(obstacleGrid[i][]==)
             {
                 dp[i][]=-;
                 continue;
             }
             if(dp[i-][]==-) dp[i][]=-;
             else dp[i][]=;
         }

         for(int j=;j<n;j++)
         {
             if(obstacleGrid[][j]==)
             {
                 dp[][j]=-;
                 continue;
             }

             if(dp[][j-]==-) dp[][j]=-;
             else dp[][j]=;
         }

         for(int i=;i<m;i++)
         {
             for(int j=;j<n;j++)
             {
                 if(obstacleGrid[i][j]==)
                 {
                     dp[i][j]=-;
                     continue;
                 }
                 if(dp[i-][j]==-&&dp[i][j-]==-) dp[i][j]=-;
                 else if(dp[i-][j]==-&&dp[i][j-]!=-) dp[i][j]=dp[i][j-];
                 else if(dp[i-][j]!=-&&dp[i][j-]==-) dp[i][j]=dp[i-][j];
                 else if(dp[i-][j]!=-&&dp[i][j-]!=-) dp[i][j]=dp[i-][j]+dp[i][j-];
             }
         }

         return dp[m-][n-]==-?:dp[m-][n-];
     }
 };

实际上不用标记也可以，dp[i][j]=0就表示了没有路

 class Solution {
 public:
     int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
         int m=obstacleGrid.size();
         int n=obstacleGrid[].size();

         int dp[][];
         //vector<vector<int>> dp(m,vector<int>(n));

         dp[][]=obstacleGrid[][]==?:;
         for(int i=;i<m;i++)
         {
             dp[i][]=obstacleGrid[i][]==?:dp[i-][];
         }
         for(int j=;j<n;j++)
         {
             dp[][j]=obstacleGrid[][j]==?:dp[][j-];
         }
         for(int i=;i<m;i++)
         {
             for(int j=;j<n;j++)
             {
                 dp[i][j]=obstacleGrid[i][j]==?:dp[i-][j]+dp[i][j-];
             }
         }

         return dp[m-][n-];
     }
 };