問題一覧 > 通常問題

No.2430 Damage Zone

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 111
作問者 : ramdosramdos / テスター : noya2noya2 Kak1_n0_taneKak1_n0_tane 👑 potato167potato167 tassei903tassei903 ponjuiceponjuice
2 ProblemId : 10002 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-08-18 21:15:01

問題文

縦 $H$ マス、横 $W$ マスのフィールドがあります。 フィールドの上から $i$ 行目, 左から $j$ 列目のマスを $(i,j)$ と呼びます。 フィールドの各マスは空き地、ダメージ床、壁のいずれかです。

  • 空き地は自由に通ることのできるマスです。
  • ダメージ床は通ると体力が $1$ 減少するマスです。
  • 壁は通ることのできないマスです。
今、ramdos 君が左上の角の空き地 $(1,1)$ にいます。 ramdos 君は今から「フィールド内を下方向に $1$ マス移動する」と「フィールド内を右方向に $1$ マス移動する」の $2$ 種類の操作をそれぞれ $0$ 回以上繰り返して右下の角の空き地 $(H,W)$ に行こうと考えています。 最初、ramdos 君の体力は $K$ です。ramdos 君は体力が $0$ になると死んでしまうので、体力の減少を $K$ 未満に抑えながら移動しようと考えています。考えられる移動経路は何通りありますか？ ただし、答えは非常に大きくなることがあるので $998244353$ で割ったあまりを求めてください。

制約

  • $H,W,K$ は整数
  • $1 \leq H,W \leq 100$
  • $1 \leq K \leq H+W$
  • $S_i$ は.,o,#のみからなる長さ $W$ の文字列で、$j$ 文字目はフィールドのマス $(i,j)$ が下記の状態であることを表す。
    • .のとき空き地である
    • oのときダメージ床である
    • #のとき壁である
  • 左上の角 $(1,1)$ と右下の角 $(H,W)$ は空き地

入力

$H\ W\ K$
$S_1$
$\vdots$
$S_H$

出力

答えを $998244353$ で割ったあまりを1行に出力してください。

サンプル

サンプル1
入力
5 5 2
.....
.o...
.....
...o.
.....
出力
46

すべての移動経路 $70$ 通りのうち、体力が $2$ 減る移動経路は $24$ 通りあるので出力すべき答えは $46$ です。

サンプル2
入力
3 3 1
...
...
...
出力
6

移動経路は $_4C_2$ で $6$ 通りです。

サンプル3
入力
40 40 15
...o##..o..........o.o.......o....#.....
..o..........o.........#...#........o...
..##................o....o#.o....#.o....
...#....o.......o.......o...#.....o.....
..o.o........#o...##.#....o..o......o...
...#..o......o.................o........
....o....oo....#..........o.............
#o..........o........o...........o....##
#....oo...#.......o#..........o.........
o....o.o#.......o..o.oo#....o#.o#o......
..............#..o...o............o.....
o.....ooo........o......o....o......o...
......#.o...............#.....o...ooo...
.....#.o..#........o.......#.o.......#..
........#......o#.................#o....
.......##..o.....oo.....#....#........o.
...#.o....o...o...#o..o...o#....#.......
...o.o.......o....##.oo#......o.........
.......o......o..........o..o....#.#...o
.o.......o#.ooo...o.......o......oo##...
.o...................oo#..#o....o.......
oo...o.#......................o......o..
....o................#..................
....o...............o.......#.........#.
..........#..o.....o.........#..#o...#o.
...........#.o........#......o.o........
...o..o..#.........oo.o..o#....#o.......
#.#.....##.#.o#.....#.....o.o......o....
.#..#.#o....................#.....o.....
..o...................#.#.....#.........
.o..o.#o...o..o.o.o..........ooo.......o
....o..o#.........o.o.o.o.#.oo..o.......
o..o..#....o...#.....oo.......o....#...o
.o....#.o...o...o....#..o.#...ooo......o
...o.....##......#.oo.......#.o...o.....
.....o.....o.#o......#.............o..o.
......o...........o..#oo...o..........o.
#.....##..o......................oo...o.
..................o....#o......o...o....
...............o.o...o#...o.o..o....oo..
出力
894449985

$998244353$ で割ったあまりを求めることに注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。