結果

問題 No.2003 Frog on Grid
ユーザー gew1fw
提出日時 2025-06-12 20:01:01
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,614 bytes
コンパイル時間 210 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 82,944 KB
最終ジャッジ日時 2025-06-12 20:04:34
合計ジャッジ時間 4,821 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
MOD = 998244353

def main():
    H, W, K = map(int, sys.stdin.readline().split())
    grid = [sys.stdin.readline().strip() for _ in range(H)]
    
    # 转换为0-based索引
    grid = [list(row) for row in grid]
    dp = [[0] * W for _ in range(H)]
    pre = [[0] * W for _ in range(H)]
    
    # 初始化起点
    if grid[0][0] == '.':
        dp[0][0] = 1
    else:
        print(0)
        return
    
    # 前缀和初始化
    pre[0][0] = dp[0][0]
    for i in range(H):
        for j in range(W):
            if i == 0 and j == 0:
                continue
            # 计算当前点的前缀和
            pre[i][j] = dp[i][j]
            if i > 0:
                pre[i][j] += pre[i-1][j]
                pre[i][j] %= MOD
            if j > 0:
                pre[i][j] += pre[i][j-1]
                pre[i][j] %= MOD
            if i > 0 and j > 0:
                pre[i][j] -= pre[i-1][j-1]
                pre[i][j] %= MOD
    
    for i in range(H):
        for j in range(W):
            if i == 0 and j == 0:
                continue
            if grid[i][j] == '#':
                dp[i][j] = 0
                continue
            
            max_s = K
            total = 0
            # 找到最小的i'和j'，使得i' >= i - max_a, j' >= j - max_b
            # 其中max_a + max_b <= K
            # 我们需要计算区域 (i' >= i - a, j' >= j - b)，a + b <= K
            # 这个区域可以用前缀和数组来计算
            min_i = max(0, i - K)
            min_j = max(0, j - K)
            
            # 我们需要找到所有点 (x, y) 满足 x >= i - K, y >= j - K, 且 (i - x) + (j - y) <= K
            # 这个条件可以重写为 x >= i - (K - (j - y))
            # 但这样处理可能比较复杂，因此我们采用暴力枚举的方式，这在K较小时是可行的
            # 注意：这里可能需要优化，但暂时假设K不是非常大
            
            # 枚举a的可能值
            for a in range(0, K+1):
                max_b = K - a
                for b in range(0, max_b+1):
                    x = i - a
                    y = j - b
                    if x >= 0 and y >= 0 and grid[x][y] == '.':
                        total += dp[x][y]
                        total %= MOD
            dp[i][j] = total % MOD
            
            # 更新前缀和数组
            pre[i][j] = (pre[i-1][j] if i > 0 else 0) + (pre[i][j-1] if j > 0 else 0) - (pre[i-1][j-1] if i > 0 and j > 0 else 0) + dp[i][j]
            pre[i][j] %= MOD
    
    print(dp[H-1][W-1] % MOD)

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