結果

問題 No.2003 Frog on Grid
コンテスト
ユーザー qwewe
提出日時 2025-04-24 12:29:49
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,532 bytes
コンパイル時間 172 ms
コンパイル使用メモリ 82,652 KB
実行使用メモリ 110,192 KB
最終ジャッジ日時 2025-04-24 12:31:35
合計ジャッジ時間 5,890 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

H, W, K = map(int, input().split())
grid = []
for _ in range(H):
    grid.append(input().strip())

# Convert grid to 1-based indices
dp = [[0] * (W + 2) for _ in range(H + 2)]
row_pre = [[0] * (W + 2) for _ in range(H + 2)]
pre = [[0] * (W + 2) for _ in range(H + 2)]

# Initialize dp[1][1]
if grid[0][0] == '.':
    dp[1][1] = 1
else:
    print(0)
    exit()

row_pre[1][1] = dp[1][1]
pre[1][1] = dp[1][1]

for i in range(1, H + 1):
    for j in range(1, W + 1):
        if i == 1 and j == 1:
            continue
        if grid[i-1][j-1] == '#':
            dp[i][j] = 0
            row_pre[i][j] = row_pre[i][j-1]
            pre[i][j] = (pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + dp[i][j]) % MOD
            continue
        
        T = i + j - K
        sum_less = 0
        if T > 1:
            x_max = min(i, T - 2)
            for x in range(1, x_max + 1):
                y_max = min(j, T - x - 1)
                if y_max < 1:
                    continue
                sum_less += row_pre[x][y_max]
                if sum_less >= MOD:
                    sum_less -= MOD
                elif sum_less < 0:
                    sum_less += MOD
            sum_less %= MOD
        
        current = (pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + dp[i][j]) % MOD
        total = (current - sum_less) % MOD
        dp[i][j] = total
        
        row_pre[i][j] = (row_pre[i][j-1] + dp[i][j]) % MOD
        pre[i][j] = (pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + dp[i][j]) % MOD

print(dp[H][W] % MOD)
0