No.3071 Double Speedrun
タグ : / 解いたユーザー数 55
作問者 : 👑
AngrySadEight
/ テスター :
👑 
seekworser
hamamu
問題文
$H$ 行 $W$ 列のマス目があります．マス目の状態は $H$ 個の長さ $W$ の文字列 $S_1, S_2, \dots, S_H$ で表され，$S_i$ の $j$ 文字目が # であれば壁が置かれていることを，. であれば置かれていないことを表します．なお，$S_{i,j}$ で $S_i$ の $j$ 文字目を表します．
Alice と Bob は，マス $(1, 1)$ からスタートし，次の $2$ 種類の移動のどちらかを繰り返すことにより，ゴールであるマス $(H, W)$ を目指します．
- マス $(i, j)$ からマス $(i + 1, j)$ へ移動する．この移動は，マス $(i + 1, j)$ が存在し，かつ壁が置かれていない場合にのみ行える．
- マス $(i, j)$ からマス $(i, j + 1)$ へ移動する．この移動は，マス $(i, j + 1)$ が存在し，かつ壁が置かれていない場合にのみ行える．
なお，Alice は最初必ずマス $(1, 1)$ からマス $(2, 1)$ への移動を行い，Bob は最初必ずマス $(1, 1)$ からマス $(1, 2)$ への移動を行います．
スムーズに移動を行いたい $2$ 人は，マス $(1, 1)$ とマス $(H, W)$ 以外のマスに対して，$2$ 人ともが通ったマスが存在しないようにしたいです．
そのような $2$ 人の移動方法の総数を $998244353$ で割った余りを求めてください．
なお，$2$ つの移動方法は，あるマスが存在し，一方では Alice または Bob のどちらかが通ったが，もう一方では通らなかった場合に区別されます．
制約
- $H, W$ は整数
- $2 \leq H, W \leq 400$
- $S_i$ は
#または.からなる長さ $W$ の文字列 - $S_{1, 1}, S_{1, 2}, S_{2, 1}, S_{H, W}$ は全て
.
入力
入力は以下の形式で標準入力から与えられる．
$H$ $W$ $S_1$ $S_2$ $\vdots$ $S_H$
出力
$2$ 人の移動方法の数を $998244353$ で割った余りを出力せよ．
サンプル
サンプル1
入力
4 4 .... .#.. .... #...
出力
5
例えば，次の移動方法は条件を満たします．
- Alice が $(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (4, 2) \rightarrow (4, 3) \rightarrow (4, 4)$ の順に移動する．
- Bob が $(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4) \rightarrow (4, 4)$ の順に移動する．
この移動方法は，Alice と Bob の両方が通ったマスがマス $(1, 1)$ およびマス $(4, 4)$ 以外に存在しないため条件を満たします．
そのような移動方法はこれ以外にも $4$ 通りあり，計 $5$ 通りの移動方法があります．
サンプル2
入力
3 3 ..# ... #..
出力
0
条件を満たす移動方法は存在しません．
サンプル3
入力
12 12 ............ ............ ............ ............ ............ ....#..#.... ....#..#.... ............ ............ ............ ............ ............
出力
188685391
$998244353$ で割った余りを出力してください．
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。