Unique Paths II 115

Question

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.

Notice

m and n will be at most 100.

Example

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[ [0,0,0], [0,1,0], [0,0,0] ]

The total number of unique paths is 2.

Solution

做法和Unique PathsI一样，不同点在于当遇到障碍物的时候直接将该点路径数设为0。

初始化：

uniquePath[0][0] = 1, 
当(i,0)不为障碍物时
uniquePath[i][0]=uniquePath[i-1][0], 否则等于0
当(0,j)不为障碍物时
uniquePath[0][j]=uniquePath[0][j-1]，否则等于0

状态函数：

uniquePath[i][j]=uniquePath[i-1][j]+uniquePath[i][j-1] 当（i，j）不为障碍物时
uniquePath[i][j]=0 当（i，j）为障碍物时

代码如下：

public class Solution {
    /**
     * @param obstacleGrid: A list of lists of integers
     * @return: An integer
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // write your code here
        if(obstacleGrid == null || obstacleGrid.length == 0){
            return 0;
        }

        if(obstacleGrid[0] == null || obstacleGrid[0].length == 0){
            return 0;
        }

        if(obstac leGrid[0][0] == 1){
            return 0;
        }

        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] uniquePath2 = new int[m][n];
        uniquePath2[0][0] = 1;

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

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

        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(obstacleGrid[i][j] != 1){
                    uniquePath2[i][j] = uniquePath2[i][j - 1] + uniquePath2[i - 1][j];
                }else{
                    uniquePath2[i][j] = 0;
                }
            }
        }

        return uniquePath2[m - 1][n - 1];
    }
}