leetcodesolutions/code/63.unique-paths-ii.java at main · Raghuram42/leetcodesolutions · GitHub

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
64
65
66
67
68
69
70
71
72
73
74
75
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
         if(m == 0)
           return 0;
        int n = obstacleGrid[0].length;
        if(m == 1 && n == 0)
           return 1;
       // if(m >= 1 && n >= 1 &&  obstacleGrid[0][0] == 1)
       //     return 0;
        int[][] dp = new int[obstacleGrid.length][obstacleGrid[0].length];


         for(int i=0;i<m;i++){
                if(obstacleGrid[i][0] == 1)
                    break;

                      dp[i][0] = 1;

            //System.out.println(i+" "+j+" "+ obstacleGrid[i][j]+" "+dp[i][j]);
            }


      for(int j=0;j<n;j++){
                if(obstacleGrid[0][j] == 1)
                    break;
                dp[0][j] = 1;
            }


        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
   //      System.out.println(i+" "+j+" before "+dp[i][j]);
                if(obstacleGrid[i][j] != 1){
                    if(obstacleGrid[i][j-1] != 1)
                   dp[i][j] += dp[i][j-1];
                    if(obstacleGrid[i-1][j] != 1)
                        dp[i][j] += dp[i-1][j];
                }
          //    System.out.println(i+" "+j+" after "+dp[i][j]);
            }
        }
        return dp[m-1][n-1];
    }
}


// class Solution {
//     int res;
//    // int pp;
//     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
//         res = 0;
//      //   pp = 0;
//         if(obstacleGrid.length == 1 && obstacleGrid[0].length == 0)
//             return 1;
//         uniq(obstacleGrid, 0, 0);
//         System.out.println(pp);
//         return res;
//     }
//     public void uniq(int[][] grid, int i, int j){

//         if(i < grid.length && i>=0 && j >=0 && j < grid[0].length){
//        //     pp++;
//             if(grid[i][j] == 1)
//                 return;
//         if(i == grid.length-1 && j == grid[0].length-1){
//                 res++;
//             return;
//         }
//          //   System.out.println(i+" "+j+" "+res);
//             uniq(grid, i, j+1);
//             uniq(grid, i+1, j);
//         }
//     }
// }