-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathUnique path 2
More file actions
63 lines (61 loc) · 1.66 KB
/
Unique path 2
File metadata and controls
63 lines (61 loc) · 1.66 KB
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
public:
int all_path(vector<vector<int>>&obstacleGrid,int n,int m,int i,int j,vector<vector<int>>&dp){
if(i==n-1 and j==m-1 and obstacleGrid[i][j]==0){
return 1;
}
if(i>=n or j>=m or obstacleGrid[i][j]==1){
return 0;
}
if(dp[i][j]!=-1){
return dp[i][j];
}
return dp[i][j]=all_path(obstacleGrid,n,m,i+1,j,dp)+all_path(obstacleGrid,n,m,i,j+1,dp);
}
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int n=obstacleGrid.size();
int m=obstacleGrid[0].size();
// vector<vector<int>>dp(n,vector<int>(m,-1));
// return all_path(obstacleGrid,n,m,0,0,dp);
int dp[n][m];
int obs=INT_MAX;
for(int i=0;i<m;i++){
if(obstacleGrid[0][i]==1){
obs=i;
break;
}
}
for(int i=0;i<m;i++){
if(i>=obs){
dp[0][i]=0;
}else{
dp[0][i]=1;
}
}
obs=INT_MAX;
for(int i=0;i<n;i++){
if(obstacleGrid[i][0]==1){
obs=i;
break;
}
}
for(int i=0;i<n;i++){
if(i>=obs){
dp[i][0]=0;
}else{
dp[i][0]=1;
}
}
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
if(obstacleGrid[i][j]==1){
dp[i][j]=0;
continue;
}else{
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
}
return dp[n-1][m-1];
}
};