A6922. 网格路径计数
编程题
普及-
知识点
题目描述
给定一个 $H \times W$ 的网格。每个格子要么是可以通过的 .，要么是障碍 #。你从左上角格子 $(1,1)$ 出发，只能向右或向下移动，问有多少种不同的走法能够到达右下角格子 $(H,W)$。答案对 $10^9+7$ 取模。
如果起点或终点是障碍，则不可达，答案为 $0$。
如果起点或终点是障碍，则不可达，答案为 $0$。
输入格式
第一行包含两个整数 $H, W$。
接下来 $H$ 行，每行一个长度为 $W$ 的仅由 . 和 # 组成的字符串，表示网格。其中 . 表示可走，# 表示障碍。
接下来 $H$ 行，每行一个长度为 $W$ 的仅由 . 和 # 组成的字符串，表示网格。其中 . 表示可走，# 表示障碍。
输出格式
输出一个整数，表示从 $(1,1)$ 到 $(H,W)$ 的不同路径数，结果对 $10^9+7$ 取模。
输入输出样例
输入 #1
3 4 ..#. .... .#..
输出 #1
4
说明/提示
$1 \le H, W \le 1000$
网格字符均为
对于样例，从起点出发存在以下路径：
- 右下右右下
- 右下右下右
- 下右右右下
- 下右右下右
故答案为 $4$。
网格字符均为
. 或 #对于样例，从起点出发存在以下路径：
- 右下右右下
- 右下右下右
- 下右右右下
- 下右右下右
故答案为 $4$。