E - Queen on Grid

Contest Duration: 2020-11-15(Sun) 12:00 - 2020-11-15(Sun) 13:40 (local time) (100 minutes) Back to Home

E - Queen on Grid Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $500$ 点

問題文

縦 $H$ マス、横 $W$ マスのグリッドがあります。上から $i$ 行目、左から $j$ 列目のマス $(i,j)$ は、 $S_{ij}$ が # のとき壁であり、. のとき道です。

マス $(1,1)$ にチェスのクイーンの駒が置いてあります。クイーンの駒は、今いる位置から右・下・右下方向に伸びる直線上にあり、壁を飛び越えずに到達できる道のマスに $1$ 手で移動することができます。

クイーンの駒がマス $(1,1)$ からマス $(H,W)$ まで移動する方法は何通りありますか？ $\bmod (10^9+7)$ で求めてください。

ただし、移動する方法が異なるとは、ある $i$ が存在して、 $i$ 手目の移動の後にクイーンの駒があるマスの位置が異なることを指します。

制約

$2 \leq H,W \leq 2000$
$S_{ij}$ は # か .
$S_{11}$ と $S_{HW}$ は .

入力

入力は以下の形式で標準入力から与えられる。

 $H$   $W$ 
 $S_{11}\ldots S_{1W}$ 
 $\vdots$ 
 $S_{H1}\ldots S_{HW}$

出力

クイーンの駒がマス $(1,1)$ から $(H,W)$ まで移動する方法の数を $\mod (10^9+7)$ で出力せよ。

入力例 1Copy

Copy

3 3
...
.#.
...

出力例 1Copy

Copy

移動方法として次の $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)$

入力例 2Copy

Copy

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

出力例 2Copy

Copy

$(1,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)$ などがあります。

入力例 3Copy

Copy

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

出力例 3Copy

Copy

13701937

移動方法の数を $\bmod (10^9+7)$ で求めてください。

Score : $500$ points

Problem Statement

We have a grid with $H$ horizontal rows and $W$ vertical columns of squares. Square $(i,j)$ , which is at the $i$ -th row from the top and $j$ -th column from the left, is wall if $S_{ij}$ is # and road if $S_{ij}$ is ..

There is a queen, the chess piece, at Square $(1, 1)$ . In one move, it can move any number of squares to the right, downwards, or diagonally to the lower right to a road square without jumping over wall squares.

In how many ways can the queen travel from Square $(1, 1)$ to Square $(H, W)$ ? Find the count modulo $(10^9+7)$ .

Here, two ways to travel are considered different if and only if there exists $i$ such that the position of the queen after the $i$ -th move is different in those two ways.

Constraints

$2 \leq H,W \leq 2000$
$S_{ij}$ is # or ..
$S_{11}$ and $S_{HW}$ are ..

Input

Input is given from Standard Input in the following format:

 $H$   $W$ 
 $S_{11}\ldots S_{1W}$ 
 $\vdots$ 
 $S_{H1}\ldots S_{HW}$

Output

Print the number of ways, modulo $(10^9+7)$ , in which the queen can travel from Square $(1, 1)$ to Square $(H, W)$ .

Sample Input 1Copy

Copy

3 3
...
.#.
...

Sample Output 1Copy

Copy

There are $10$ ways to travel, as follows:

$(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)$

Sample Input 2Copy

Copy

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

Sample Output 2Copy

Copy

From $(1,1)$ , the queen can move to $(1,2)$ , $(1,3)$ , $(2,1)$ , $(2,2)$ , $(3,1)$ , or $(4,1)$ .

One possible path to $(4,4)$ is $(1,1)\to (3,1)\to (3,2)\to (4,3)\to (4,4)$ .

Sample Input 3Copy

Copy

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

Sample Output 3Copy

Copy

13701937

Find the count modulo $(10^9+7)$ .