問題一覧 > 通常問題

No.2430 Damage Zone

レベル : / AI推定難易度 : 950 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 119
作問者 : ramdos / テスター : noya2 Kak1_n0_tane 👑 potato167 tassei903 ponjuice
お気に入りにしたユーザー ProblemId : 10002 / 自分の提出
問題文最終更新日: 2023-08-18 21:15:01
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
traP 作問ハッカソンコンテスト 001 (順位表) の他の問題:

Problem Statement

There is a field with $H$ rows and $W$ columns. The cell at the $i$-th row from the top and the $j$-th column from the left is called $(i,j)$. Each cell of the field is one of an empty cell, a damage floor, or a wall.

  • An empty cell is a cell that can be passed through freely.
  • A damage floor is a cell that decreases stamina by $1$ when passed through.
  • A wall is a cell that cannot be passed through.
Now, ramdos is at the top-left corner $(1,1)$, which is an empty cell. He intends to reach the bottom-right corner $(H,W)$, which is an empty cell, by repeating "move down by $1$ cell within the field" and "move right by $1$ cell within the field", these $2$ types of operations, each $0$ or more times. Initially, ramdos's stamina is $K$. Since ramdos dies when his stamina becomes $0$, he intends to move while keeping the decrease in stamina below $K$. How many possible movement paths are there? Since the answer can be very large, find it modulo $998244353$.

Constraints

  • $H,W,K$ are integers
  • $1 \leq H,W \leq 100$
  • $1 \leq K \leq H+W$
  • $S_i$ is a string of length $W$ consisting only of .,o,#, and its $j$-th character represents the state of the cell $(i,j)$ of the field as follows.
    • . means it is an empty cell
    • o means it is a damage floor
    • # means it is a wall
  • The top-left corner $(1,1)$ and the bottom-right corner $(H,W)$ are empty cells

Input

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

Output

Output the answer modulo $998244353$ on 1 line.

Sample

Sample 1
Input
5 5 2
.....
.o...
.....
...o.
.....
Output
46

Out of all $70$ movement paths, there are $24$ paths on which stamina decreases by $2$, so the answer to output is $46$.

Sample 2
Input
3 3 1
...
...
...
Output
6

The number of movement paths is $_4C_2$, which is $6$.

Sample 3
Input
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..
Output
894449985

Note that you must find the answer modulo $998244353$.

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