Submission #19695264

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import numpy as np
H, W, K = map(int, input().split())
MOD = 998244353
cells = {}
for _ in range(K):
    h, w, c = input().split()
    h, w = int(h) - 1, int(w) - 1
    cells[(h, w)] = c
# dp[h][w][k] := ロボットが(0, 0)から出発して空白マスをk箇所通って(h - 1, w - 1)に到達するような経路の個数
dp = np.zeros((H + W + 1, H + 1, W + 1), dtype='i')
dp[0, 0, 0] = 1
# 配るDP
for h in range(H):
    for w in range(W):
        v = cells.get((h, w), None)
        for k in range(H + W):
            if v is None:
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import numpy as np

H, W, K = map(int, input().split())
MOD = 998244353

cells = {}
for _ in range(K):
    h, w, c = input().split()
    h, w = int(h) - 1, int(w) - 1
    cells[(h, w)] = c

# dp[h][w][k] := ロボットが(0, 0)から出発して空白マスをk箇所通って(h - 1, w - 1)に到達するような経路の個数
dp = np.zeros((H + W + 1, H + 1, W + 1), dtype='i')
dp[0, 0, 0] = 1

# 配るDP
for h in range(H):
    for w in range(W):
        v = cells.get((h, w), None)
        for k in range(H + W):
            if v is None:
                dp[k + 1, h + 1, w] += dp[k, h, w]
                dp[k + 1, h, w + 1] += dp[k, h, w]
            if v in ['D', 'X']:
                dp[k, h + 1, w] += dp[k, h, w]
            if v in ['R', 'X']:
                dp[k, h, w + 1] += dp[k, h, w]

ans = 0
for k in range(H + W + 1):
    ans += dp[k, H - 1, W - 1] * pow(2, k, MOD) * pow(3, H * W - K - k)
    ans %= MOD
print(int(ans))

Submission Info

Judge Result