@@ -0,0 +1,1624 @@
+/**%0A *%09Follow up for %22Unique Paths%22:%0A *%0A *%09Now consider if some obstacles are added to the grids. How many unique paths would there be?%0A *%0A *%09An obstacle and empty space is marked as 1 and 0 respectively in the grid.%0A *%0A *%09For example,%0A *%09There is one obstacle in the middle of a 3x3 grid as illustrated below.%0A *%0A *%09%5B%0A * %09%09%5B0,0,0%5D,%0A * %09%09%5B0,1,0%5D,%0A * %09%09%5B0,0,0%5D%0A *%09%5D%0A *%09The total number of unique paths is 2.%0A *%0A *%09Author: matao%0A *%0A */%0A%0Apublic class UniquePathsII %7B%0A%09public static int uniquePathsWithObstacles(int%5B%5D%5B%5D obstacleGrid) %7B%0A        if(obstacleGrid == null %7C%7C obstacleGrid.length == 0 %7C%7C obstacleGrid%5B0%5D.length == 0) %7B%0A        %09return 0;%0A        %7D%0A        int M = obstacleGrid.length;%0A        int N = obstacleGrid%5B0%5D.length;%0A%0A        int%5B%5D%5B%5D sum = new int%5BM%5D%5BN%5D;%0A        for (int i = 0; i %3C M; i++) %7B%0A            if (obstacleGrid%5Bi%5D%5B0%5D != 1) %7B%0A                sum%5Bi%5D%5B0%5D = 1;%0A            %7D else %7B%0A                break;%0A            %7D%0A        %7D%0A        %0A        for (int i = 0; i %3C N; i++) %7B%0A            if (obstacleGrid%5B0%5D%5Bi%5D != 1) %7B%0A                sum%5B0%5D%5Bi%5D = 1; %0A            %7D else %7B%0A                break;%0A            %7D%0A        %7D%0A%0A        for(int i = 1; i %3C M; i++) %7B%0A        %09for (int j = 1; j %3C N; j++) %7B%0A        %09%09if(obstacleGrid%5Bi%5D%5Bj%5D == 1) %7B%0A        %09%09%09sum%5Bi%5D%5Bj%5D = 0;%0A        %09%09%7D else %7B%0A        %09%09%09sum%5Bi%5D%5Bj%5D = sum%5Bi-1%5D%5Bj%5D + sum%5Bi%5D%5Bj-1%5D;%0A        %09%09%7D%0A        %09%7D%0A        %7D%0A        return sum%5BM-1%5D%5BN-1%5D;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A    %09int%5B%5D%5B%5D obstacleGrid = %7B%7B0, 0, 0%7D,%0A    %09%09%09%09%09%09%09%7B0, 1, 0%7D,%0A    %09%09%09%09%09%09%09%7B0, 0, 0%7D%7D;%0A    %09System.out.println(uniquePathsWithObstacles(obstacleGrid));%0A    %7D%0A%7D

add Unique Paths II solution