AT_dp_h Grid 1

题目描述

有一个高 $H$ 行、宽 $W$ 列的网格。第 $i$ 行第 $j$ 列的格子用 $(i, j)$ 表示。

对于每个 $i, j$（$1 \leq i \leq H$，$1 \leq j \leq W$），格子 $(i, j)$ 的信息由字符 $a_{i, j}$ 给出。如果 $a_{i, j}$ 为 .，则格子 $(i, j)$ 是空格；如果 $a_{i, j}$ 为 #，则格子 $(i, j)$ 是墙。保证格子 $(1, 1)$ 和 $(H, W)$ 都是空格。

太郎君从格子 $(1, 1)$ 出发，每次只能向右或向下移动到相邻的空格，目标是到达格子 $(H, W)$。

请问从 $(1, 1)$ 到 $(H, W)$ 的路径有多少种？由于答案可能非常大，请输出答案对 $10^9 + 7$ 取模的结果。

输入格式

输入从标准输入读入，格式如下：

$H$ $W$
$a_{1, 1}$ $\ldots$ $a_{1, W}$
$\vdots$
$a_{H, 1}$ $\ldots$ $a_{H, W}$

输出格式

输出从 $(1, 1)$ 到 $(H, W)$ 的路径数，对 $10^9 + 7$ 取模。

输入输出样例 #1

输入 #1

3 4
...#
.#..
....

输出 #1

3

输入输出样例 #2

输入 #2

5 2
..
#.
..
.#
..

输出 #2

0

输入输出样例 #3

输入 #3

5 5
..#..
.....
#...#
.....
..#..

输出 #3

24

输入输出样例 #4

输入 #4

20 20
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................

输出 #4

345263555

说明/提示

限制条件

• $H$ 和 $W$ 是整数。
• $2 \leq H, W \leq 1000$。
• $a_{i, j}$ 只可能是 . 或 #。
• $(1, 1)$ 和 $(H, W)$ 都是空格。

样例解释 1

路径共有 $3$ 条，如下图所示。

样例解释 2

也有可能不存在任何路径。

样例解释 4

不要忘记输出答案时要对 $10^9 + 7$ 取模。

由 ChatGPT 4.1 翻译