4180: 不同路径II(Unique Paths II)
[Creator : ]
Description
设想有个机器人坐在 $X*Y$ 网格的左上角,坐标为 $(0,\ 0)$,右下角的坐标为 $(x-1,\ y-1)$。假设机器人智能只能向右、向下移动。但是在移动过程中,有些位置是障碍,无法走入。机器人从 $(0,\ 0)$ 到 $(X-1,\ Y-1)$ 有多少种走法?
Input
一行,包括 $2$ 个整数 $x,\ y$,表示左下角的坐标。其中 $1≤X≤100,\ 1≤Y≤100$。
后面跟随一个 $x$ 行 $y$ 列的矩阵。数据之间用空格隔开。$0$ 表示可以通过,$1$ 表示不能通过。
后面跟随一个 $x$ 行 $y$ 列的矩阵。数据之间用空格隔开。$0$ 表示可以通过,$1$ 表示不能通过。
Output
一行,一个整数,表示有几种走法。由于答案可能会很大,答案请对 $10^9+7$ 取模。
Sample 1 Input
3 3
0 0 0
0 1 0
0 0 0
Sample 1 Output
2
$3 \times 3$ 网格的正中间有一个障碍物。
走到右下角的路径有
1. 右->右->下->下
2. 下->下->右->右
这样一共有 $2$ 条路径。
Sample 2 Input
2 2
0 1
0 0
Sample 2 Output
1
Sample 3 Input
5 2
0 0
0 0
0 0
0 1
1 0
Sample 3 Output
0
HINT
题目来源:LeetCode 63。
https://leetcode-cn.com/problems/unique-paths-ii/
https://leetcode.com/problems/unique-paths-ii/
https://leetcode-cn.com/problems/unique-paths-ii/
https://leetcode.com/problems/unique-paths-ii/