一个机器人站立在 m×n 方格的左上角（下图中标记为“Start”的位置）。

这个机器人只能向右或向下移动。机器人正在试着移动到方格的右下角（下图中标记为“Finish”的位置）。

如果方格中有一些障碍物，那么共有多少条不同的路径可以移动？

方格中障碍物用 1 表示，0 表示没有障碍物。

提示： m 与 n 最大为 100。

例一：
输入： [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
输出： 2
解释：
在 3×3 的方格中存在一个障碍物。
这里有两条路径可以到达右下角：
1. 右->右->下->下
2. 下->下->右->右

这个题和上一个题很像，同样是求路径的数量，不过这次在某些位置可能会出现障碍物，导致机器人不能通过。

如果这个障碍物只出现一次的话，那么就又是一个经典的数理统计问题，相信学过高中数学或者高数的同学都做过这种题。

在这个问题中，障碍物可能会出现多次，使用我们熟悉的数学方法就不太适合这个问题了。这次我们仍然使用动态规划来解决。

我们首先考虑第一行的情况，当第一行的某一位置有障碍物时，则其路径数量为 0，而没有障碍物时，其路径数量等于其左边位置路径数量 1 或 0。接着是考虑第一列的情况，情况和第一行类似，当第一列的某一位置有障碍物i时，其路径数量为 0，而没有障碍物时，其路径数量等于其上边位置路径数量 1 或 0。

这里说一下第一行第一列的位置，如果其有障碍物，我们就可以不用计算了，直接返回 0 就行。同理如果最后一行最后一列有障碍物，同样返回 0。第一个位置在没有障碍物的时候我们就可以将其路径数量设置为 1，然后再进入循环逐行检查。

在检查时，每一位置的路径数量等于 其上方位置的路径 与 其左方位置的路径 的和，遇到障碍物时直接将其值设为 0 即可。

/*
 * 63. Unique Paths II
 * https://leetcode.com/problems/unique-paths-ii/
 * https://www.whosneo.com/63-unique-paths-ii/
 */

public class UniquePathsWithObstacles {
    public static void main(String[] args) {
        UniquePathsWithObstacles solution = new UniquePathsWithObstacles();

        int[][] grid = new int[][]{
                {0, 0, 0},
                {0, 1, 0},
                {0, 0, 0}
        };

        System.out.println(solution.uniquePathsWithObstacles(grid));
    }

    private int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1)
            return 0;

        // 每一位置的移动路径的数量等于
        // 其上方位置的路径 与 其左方位置的路径 的和
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (i == 0 && j == 0)
                    obstacleGrid[i][j] = 1;
                else if (i == 0) // 第一行
                    obstacleGrid[0][j] = obstacleGrid[0][j] == 0 ? obstacleGrid[0][j - 1] : 0;
                else if (j == 0) // 第一列
                    obstacleGrid[i][0] = obstacleGrid[i][0] == 0 ? obstacleGrid[i - 1][0] : 0;
                else
                    obstacleGrid[i][j] = obstacleGrid[i][j] == 0 ? obstacleGrid[i][j - 1] + obstacleGrid[i - 1][j] : 0;

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

    private int uniquePathsWithObstacles2(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1)
            return 0;

        // 用一个更大的数组来存储结果，这样就无需考虑第一行或第一列的情况
        int[][] result = new int[m + 1][n + 1];
        result[1][1] = 1;

        for (int i = 1; i < m + 1; i++)
            for (int j = 1; j < n + 1; j++)
                if (i >1 || j > 1)
                    result[i][j] = obstacleGrid[i - 1][j - 1] == 0 ? result[i][j - 1] + result[i - 1][j] : 0;

        return result[m][n];
    }
}