問題一覧 > 通常問題

No.2430 Damage Zone

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

問題文

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

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

制約

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

入力

H W KH\ W\ K
S1S_1
⋮\vdots
SHS_H

出力

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

サンプル

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

すべての移動経路 7070 通りのうち、体力が 22 減る移動経路は 2424 通りあるので出力すべき答えは 4646 です。

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

移動経路は 4C2_4C_2 で 66 通りです。

サンプル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

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

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