# missjing/leetcode

Switch branches/tags
Nothing to show
Fetching contributors…
Cannot retrieve contributors at this time
89 lines (77 sloc) 2.38 KB
 problem： 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. -------------------------------------------------------------------------- solution： 思路一、用二维数组做记录 //（1）对于第1行，如果有障碍，则障碍处开始往后，方法数均为0，否则为1； //（2）对于第1列，如果有障碍，则障碍处开始往下，方法数均为0，否则为1； //（3）到达A[i][j]，如果A[i][j]有障碍，则方法数为0，否则，可以从A[i-1][j]到达A[i][j]，也可以从A[i][j-1]到达A[i][j]，可用的方法有A[i-1][j]+A[i][j-1]种。 int uniquePathsWithObstacles(vector > &obstacleGrid) { int m = obstacleGrid.size(); if(m == 0) return 0; int n = obstacleGrid[0].size(); if(n == 0) return 0; int dp[m][n]; bool isBlocked = false; for(int c = 0; c < n; ++c) { if(isBlocked == false && obstacleGrid[0][c] == 1) isBlocked = true; if(isBlocked == false) dp[0][c] = 1; else dp[0][c] = 0; } isBlocked = false; for(int r = 0; r < m; ++r) { if(isBlocked == false && obstacleGrid[r][0] == 1) isBlocked = true; if(isBlocked == false) dp[r][0] = 1; else dp[r][0] = 0; } for (int r = 1; r < m; ++r) for (int c = 1; c < n; ++c) { if(obstacleGrid[r][c] == 0) dp[r][c] = dp[r - 1][c] + dp[r][c - 1]; else dp[r][c] = 0; } return dp[m - 1][n - 1]; } 思路二、用一维数组按列记录，从底往上，从右往左。 初始时最底行从右往左，每列初始为1直到遇到有障碍，则全为0； 接着从倒数第二行一直到第一行，如果没有障碍，则dp[i]=dp[i]+dp[i+1]，否则为0 //////////////////////////////////////////// int uniquePathsWithObstacles(vector > &obstacleGrid) { int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); if(m == 0 || n == 0) return 0; vector dp(n + 1, 0); for(int i = n - 1; i >= 0; --i) if(obstacleGrid[m - 1][i] == 0) dp[i] = 1; for(int j = m - 2; j >= 0; --j) for(int i = n - 1; i >= 0; --i) dp[i] = (obstacleGrid[j][i] == 1) ? 0 : dp[i]+dp[i+1]; return dp[0]; }