結果

問題 No.2003 Frog on Grid
ユーザー gew1fw
提出日時 2025-06-12 14:50:15
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,060 bytes
コンパイル時間 438 ms
コンパイル使用メモリ 82,444 KB
実行使用メモリ 330,120 KB
最終ジャッジ日時 2025-06-12 14:53:48
合計ジャッジ時間 5,478 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 WA * 7 TLE * 1 -- * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    H = int(input[ptr]); ptr +=1
    W = int(input[ptr]); ptr +=1
    K = int(input[ptr]); ptr +=1
    grid = []
    for _ in range(H):
        grid.append(input[ptr])
        ptr +=1
    
    # Initialize dp, pre_sum, diag_sum, diag_prefix
    dp = [[0]*(W+1) for _ in range(H+1)]
    pre_sum = [[0]*(W+1) for _ in range(H+1)]
    max_s = H + W
    diag_sum = [0]*(max_s + 2)
    diag_prefix = [0]*(max_s + 2)
    
    # Starting point
    dp[1][1] = 1
    pre_sum[1][1] = 1
    diag_sum[2] = 1
    diag_prefix[2] = 1
    
    for s in range(3, max_s +1):
        current_v = s
        for i in range(1, H+1):
            j = s - i
            if j < 1 or j > W:
                continue
            if i == 1 and j == 1:
                continue
            # Check if the current cell is blocked
            if grid[i-1][j-1] == '#':
                dp[i][j] = 0
                pre_sum[i][j] = (pre_sum[i-1][j] + pre_sum[i][j-1] - pre_sum[i-1][j-1]) % MOD
                continue
            # Compute pre_sum_i_j
            pre_sum_i_j = (pre_sum[i-1][j] + pre_sum[i][j-1] - pre_sum[i-1][j-1]) % MOD
            # Calculate v_min and v_max
            v_min = 2
            v_max = s - K - 1
            if v_max >= v_min:
                sum_diags = (diag_prefix[v_max] - diag_prefix[v_min-1]) % MOD
            else:
                sum_diags = 0
            # Compute dp[i][j]
            dp_ij = (pre_sum_i_j - sum_diags) % MOD
            if dp_ij < 0:
                dp_ij += MOD
            dp[i][j] = dp_ij
            # Update pre_sum
            pre_sum[i][j] = (pre_sum[i-1][j] + pre_sum[i][j-1] - pre_sum[i-1][j-1] + dp_ij) % MOD
            # Update diag_sum
            diag_sum[current_v] = (diag_sum[current_v] + dp_ij) % MOD
        # Update diag_prefix
        if current_v >= 2:
            diag_prefix[current_v] = (diag_prefix[current_v-1] + diag_sum[current_v]) % MOD
    
    print(dp[H][W] % MOD)

if __name__ == "__main__":
    main()
0