Problem4180--不同路径II(Unique Paths II)

4180: 不同路径II(Unique Paths II)

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

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$ 表示不能通过。

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/

Source/Category