问题 E: 网格路径数
内存限制:1024 MB
时间限制:2.000 S
评测方式:文本比较
命题人:
提交:14
解决:4
题目描述
有一个$H$行$W$列的网格S,$S_{i,j}$为'#'表示此网格是一堵墙不能通行,为'.'则可以通行。你初始站在$(1,1)$处,在不碰到墙的前提下,每次可以向右走任意格,或向下走任意格,或沿对角线走任意格。请问有多少种方案到$(H,W)$?
对于任意两个方案,如果存在第$i$次移动使它的位置不同,视为不同方案。
答案对$(10^9+7)$取模。
对于任意两个方案,如果存在第$i$次移动使它的位置不同,视为不同方案。
答案对$(10^9+7)$取模。
输入
$H$ $W$
$S_{1,1}$ . . . $S_{1,W}$
.
.
.
$S_{H,1}$ . . . $S_{H,W}$
$2<=H,W<=2000$
$(1,1)$和 $(H,W)$一定不是墙
$S_{1,1}$ . . . $S_{1,W}$
.
.
.
$S_{H,1}$ . . . $S_{H,W}$
$2<=H,W<=2000$
$(1,1)$和 $(H,W)$一定不是墙
输出
输出取模后的方案数
样例输入 复制
3 3
...
.#.
...
样例输出 复制
10