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

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

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

在 3×3 的方格中存在一个障碍物。

这里有两条路径可以到达右下角：

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

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

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

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

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

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