63.不同路径II

题目

不同路劲的进阶问题。考虑网格中有障碍物，同样求从左上角到右下角的路径数。
1表示障碍物，0表示空位置。
题目连接

思路

和不同路径同样的思路，只不过要专门处理有障碍的位置。
首先，对于任何有障碍的位置，因为其不可达，所有dp=0
其次，对于第一行和第一列，如果某个位置有障碍，则其后的位置（同一行、列）都是不可达的，应该设置dp=0。

代码

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        int[][] dp = new int[m][n];

        int firstOne = -1;
        for(int i = 0; i < m; i++) {
            if(obstacleGrid[i][0] == 1) {
                firstOne = i;
                break;
            }
        }
        // System.out.println(firstOne);
        for(int i = 0; i < m; i++) dp[i][0] = 1;
        if(firstOne != -1)
            while(firstOne < m) dp[firstOne++][0] = 0;
        firstOne = -1;
        for(int j = 0; j < n; j++) {
            if(obstacleGrid[0][j] == 1) {
                firstOne = j;
                break;
            }
        }
        // System.out.println(firstOne);

        for(int j = 0; j < n; j++) dp[0][j] = 1;
        if(firstOne != -1)
            while(firstOne < n) dp[0][firstOne++] = 0;

        for(int i = 1; i < m; i++)
            for(int j = 1; j < n; j++) {
                dp[i][j] = (obstacleGrid[i][j] == 1)?0:(dp[i-1][j] + dp[i][j-1]);
            }
        return dp[m-1][n-1];
    }
}