Queen on Grid

题目描述

我们有一个由 $H$$个横向行 和$W$$ 个纵向列 方格组成的网格。 位于从上数第 $i$$行、从左数第$j$$$列的方格$(i,j)$如果$S_{ij} 为 # 则是<em>障碍</em>，如果 S_{ij}$为$.$则是<em>道路</em>。 在方格$(1, 1)$上有一枚皇后（棋子）。在一次移动中，它可以向右、向下或向右下对角线任意格数移动到一个道路方格，但不能越过障碍方格。 皇后从方格$(1, 1)$到方格$(H, W)$有多少种走法？请给出模$(10^9+7)$的结果。 这里，当且仅当存在某个$i$使得两种走法在第$i$ 次移动后皇后所处的位置不同，则认为这两种走法是不同的。

输入格式

输入从标准输入按如下格式给出： $H$ $W$ $S_{11}\ldots S_{1W}$ $\vdots$ $S_{H1}\ldots S_{HW}$

输出格式

打印皇后从方格 $(1, 1)$ 到方格 $(H, W)$ 的走法数，对 $(10^9+7)$ 取模。

3 3
...
.#.
...

10

4 4
...#
....
..#.
....

84

8 10
..........
..........
..........
..........
..........
..........
..........
..........

13701937

提示

$2 \leq H,W \leq 2000$ $S_{ij}$ 是 # 或 $.$。 $S_{11}$ 和 $S_{HW}$ 是 $.$。共有 $10$ 种走法，如下所示：

$(1,1)\to (1,2)\to (1,3)\to (2,3)\to (3,3)$ $(1,1)\to (1,2)\to (1,3)\to (3,3)$ $(1,1)\to (1,2)\to (2,3)\to (3,3)$ $(1,1)\to (1,2)\to (1,3)\to (2,3)\to (3,3)$ $(1,1)\to (1,3)\to (3,3)$ $(1,1)\to (2,1)\to (3,1)\to (3,2)\to (3,3)$ $(1,1)\to (2,1)\to (3,1)\to (3,3)$ $(1,1)\to (2,1)\to (3,2)\to (3,3)$ $(1,1)\to (3,1)\to (3,2)\to (3,3)$ $(1,1)\to (3,1)\to (3,3)$
从 $(1,1)$ 出发，皇后可以移动到 $(1,2)$、$(1,3)$、$(2,1)$、$(2,2)$、$(3,1)$ 或 $(4,1)$。 到 $(4,4)$ 的一个可能路径是 $(1,1)\to (3,1)\to (3,2)\to (4,3)\to (4,4)$。
请对 $(10^9+7)$ 取模后给出结果。

标签: AtCoder|abc183E

来源

AtCoder|abc183E