Unique Paths II Problem: You are given an m x n
integer array grid
. There is a robot initially located at the top-left corner (i.e., grid[0][0]
). The robot tries to move to the bottom-right corner (i.e., grid[m-1][n-1]
). The robot can only move either down or right at any point in time.
An obstacle and space are marked as 1
or 0
respectively in grid
. A path that the robot takes cannot include any square that is an obstacle.
Return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The testcases are generated so that the answer will be less than or equal to 2 * 109
.
Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] Output: 2 Explanation: There is one obstacle in the middle of the 3x3 grid above. There are two ways to reach the bottom-right corner: 1. Right -> Right -> Down -> Down 2. Down -> Down -> Right -> Right
Table of Contents
Unique Paths II Problem Solution
Problem Solution In Python
class Solution:
def uniquePathsWithObstacles(self, og: List[List[int]]) -> int:
if og[0][0]==1:
return 0
else:
og[0][0]=1
for i in range(1,len(og)):
if og[i][0]!=1:
og[i][0]=og[i-1][0]
else:
og[i][0]=0
for i in range(1,len(og[0])):
if og[0][i]!=1:
og[0][i]=og[0][i-1]
else:
og[0][i]=0
for i in range(1,len(og)):
for j in range(1,len(og[0])):
if og[i][j]!=1:
og[i][j]=og[i-1][j]+og[i][j-1]
else:
og[i][j]=0
return og[-1][-1]
Problem Solution In Java
public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] s = new int[m][n];
s[0][0] = obstacleGrid[0][0]==0 ? 1:0;
if(s[0][0] == 0) return 0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(obstacleGrid[i][j] == 1) s[i][j] = 0;
else if(i==0){
if(j>0) s[i][j] = s[i][j-1];
}
else if(j==0){
if(i>0) s[i][j] = s[i-1][j];
}
else s[i][j] = s[i-1][j] + s[i][j-1];
}
}
return s[m-1][n-1];
}
}
Problem Solution In C++
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
for(int i = 0; i < obstacleGrid.size(); i++) {
for (int j = 0; j < obstacleGrid[i].size(); j++) {
if (obstacleGrid[i][j] == 1) {
obstacleGrid[i][j] = 0;
} else if (i == 0 && j == 0) {
obstacleGrid[i][j] = 1;
} else if (i == 0) {
obstacleGrid[i][j] = obstacleGrid[i][j-1];
} else if (j == 0) {
obstacleGrid[i][j] = obstacleGrid[i-1][j];
} else {
long long int temp = (long long int)obstacleGrid[i-1][j] + (long long int)obstacleGrid[i][j-1];
if (temp > INT_MAX) {
obstacleGrid[i][j] = -1;
} else {
obstacleGrid[i][j] = temp;
}
}
}
}
return obstacleGrid[obstacleGrid.size()-1][obstacleGrid[0].size()-1];
}
};
Problem Solution In C
int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridRowSize, int obstacleGridColSize) {
int i, j;
int dp[101][101];
memset(dp, 0, sizeof(dp));
for(i = 1; i <= obstacleGridRowSize; i++){
for(j = 1; j <= obstacleGridColSize; j++){
if(obstacleGrid[i - 1][j - 1] != 1 && i == 1 && j == 1){
dp[i][j] = 1;
}else if(obstacleGrid[i - 1][j - 1] != 1){
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[obstacleGridRowSize][obstacleGridColSize];
}