Title: Unique Paths II Source: leetcode.com
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 3×3 grid as illustrated below.
|
1 2 3 4 5 |
[ [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.
Java solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
/* https://leetcode.com/problems/unique-paths-ii/ */ class UniquePathsII { public static void main(String args[]) { int[][] obstacleGrid = {{0, 0, 0}, {0, 1, 1}, {0, 1, 0}}; UniquePathsII solution = new UniquePathsII(); System.out.println(solution.uniquePathsWithObstacles(obstacleGrid)); } public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m = obstacleGrid.length; int n = obstacleGrid[obstacleGrid.length-1].length; int[][] dp = new int[m][n]; for(int i=0;i<m;i++) { for(int j=0;j<n;j++) dp[i][j]=-1; } helper(m-1, n-1, dp, obstacleGrid); return dp[m-1][n-1]==-1?0:dp[m-1][n-1]; } int helper(int i, int j, int[][] dp, int[][] obstacleGrid) { if(i<0 ||j<0 || obstacleGrid[i][j]==1) return 0; if(i==0 && j==0) { return dp[i][j]=1; } else { dp[i][j] = dp[i][j]!=-1?dp[i][j]:(helper(i-1, j, dp, obstacleGrid) + helper(i, j-1, dp, obstacleGrid)); return dp[i][j]; } } } |
Python solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
''' https://leetcode.com/problems/unique-paths-ii/ ''' class Solution(object): def uniquePathsWithObstacles(self, obstacleGrid): """ :type obstacleGrid: List[List[int]] :rtype: int """ m = len(obstacleGrid) n = len(obstacleGrid[0]) if obstacleGrid[0][0] == 1: return 0 flag = True for i in range(n): if obstacleGrid[0][i] == 1: obstacleGrid[0][i] = -1 flag = False else: if flag: obstacleGrid[0][i] = 1 flag = True for i in range(1,m): if obstacleGrid[i][0] == 1: obstacleGrid[i][0] = -1 flag = False else: if flag: obstacleGrid[i][0] = 1 for i in range(1,m): for j in range(1,n): if obstacleGrid[i][j] == 1: obstacleGrid[i][j] = -1 else: if obstacleGrid[i-1][j] > 0 and obstacleGrid[i][j-1] > 0: obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1] else: obstacleGrid[i][j] = max(obstacleGrid[i-1][j], obstacleGrid[i][j-1]) if obstacleGrid[m-1][n-1] == -1: return 0 return obstacleGrid[m-1][n-1] |