No.3071 Double Speedrun
タグ : / 解いたユーザー数 59
作問者 : 👑
seekworser
👑 
hamamu
Problem Statement
There is a grid with $H$ rows and $W$ columns. The state of the grid is represented by $H$ strings $S_1, S_2, \dots, S_H$ of length $W$. If the $j$-th character of $S_i$ is #, a wall is placed there; if it is ., no wall is placed there. Here, $S_{i,j}$ denotes the $j$-th character of $S_i$.
Alice and Bob start from cell $(1, 1)$ and aim for the goal, cell $(H, W)$, by repeating either of the following $2$ types of moves.
- Move from cell $(i, j)$ to cell $(i + 1, j)$. This move can be made only if cell $(i + 1, j)$ exists and has no wall placed on it.
- Move from cell $(i, j)$ to cell $(i, j + 1)$. This move can be made only if cell $(i, j + 1)$ exists and has no wall placed on it.
Note that Alice's first move must be from cell $(1, 1)$ to cell $(2, 1)$, and Bob's first move must be from cell $(1, 1)$ to cell $(1, 2)$.
The $2$ people want to move smoothly, so they want there to be no cell, among the cells other than cell $(1, 1)$ and cell $(H, W)$, that both of the $2$ people pass through.
Find the total number of such ways for the $2$ people to move, modulo $998244353$.
Here, $2$ ways of moving are distinguished if there exists a cell that Alice or Bob passed through in one of them but that was not passed through in the other.
Constraints
- $H, W$ are integers
- $2 \leq H, W \leq 400$
- $S_i$ is a string of length $W$ consisting of
#or. - $S_{1, 1}, S_{1, 2}, S_{2, 1}, S_{H, W}$ are all
.
Input
The input is given from Standard Input in the following format.
$H$ $W$ $S_1$ $S_2$ $\vdots$ $S_H$
Output
Output the number of ways for the $2$ people to move, modulo $998244353$.
Sample
Sample 1
Input
4 4 .... .#.. .... #...
Output
5
For example, the following way of moving satisfies the condition.
- Alice moves in the order $(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (4, 2) \rightarrow (4, 3) \rightarrow (4, 4)$.
- Bob moves in the order $(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4) \rightarrow (4, 4)$.
This way of moving satisfies the condition because no cell other than cell $(1, 1)$ and cell $(4, 4)$ is passed through by both Alice and Bob.
There are $4$ other such ways of moving, for a total of $5$ ways.
Sample 2
Input
3 3 ..# ... #..
Output
0
No way of moving satisfies the condition.
Sample 3
Input
12 12 ............ ............ ............ ............ ............ ....#..#.... ....#..#.... ............ ............ ............ ............ ............
Output
188685391
Output the answer modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。