AT_abc183_e [ABC183E] Queen on Grid

题目描述

有一个高 $H$ 行、宽 $W$ 列的网格。第 $i$ 行第 $j$ 列的格子 $(i, j)$，如果 $S_{ij}$ 是 #，则为墙，否则为道路。

在格子 $(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$ 取模。

输入输出样例 #1

输入 #1

3 3
...
.#.
...

输出 #1

10

输入输出样例 #2

输入 #2

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

输出 #2

84

输入输出样例 #3

输入 #3

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

输出 #3

13701937

说明/提示

限制

• $2 \leq H, W \leq 2000$
• $S_{ij}$ 只可能为 # 或 .
• $S_{11}$ 和 $S_{HW}$ 均为 .

样例解释 1

存在如下 $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,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)$

样例解释 2

从 $(1,1)$ 出发，可以一步到达 $(1,2)$、$(1,3)$、$(2,1)$、$(2,2)$、$(3,1)$、$(4,1)$ 中的任意一个。例如，$(1,1)\to (3,1)\to (3,2)\to (4,3)\to (4,4)$ 是到 $(4,4)$ 的一种路径。

样例解释 3

请对路径数取 $10^9+7$ 的模输出。

由 ChatGPT 4.1 翻译