题解 | 旅行者的大逃脱

import sys

input = sys.stdin.readline
inf = float('inf')
MOD = 998244353
for _ in range(int(input())):
    n, m, q, k = map(int, input().split())
    listener = [[] for _ in range(k)]
    for _ in range(q):
        x, y, t = map(lambda x: int(x)-1, input().split())
        if t < k:
            listener[t].append((x, y))

    dp = [[0]*m for _ in range(n)]
    dp[0][0] = 1

    total_ways = 0
    shortest_time = -1
    vis = [[0] * m for _ in range(n)]

    for _ in range(k):

        for r, c in listener[_]:
            vis[r][c] = 1

        nxt = [[0]*m for _ in range(n)]
        for i in range(n):
            prev = 0
            for j in range(m):
                if vis[i][j]:
                    prev = 0
                    continue
                nxt[i][j] = (nxt[i][j]+prev) % MOD
                prev = (prev+dp[i][j]) % MOD

        for j in range(m):
            prev = 0
            for i in range(n):
                if vis[i][j]:
                    prev = 0
                    continue
                nxt[i][j] = (nxt[i][j]+prev) % MOD
                prev = (prev+dp[i][j]) % MOD
        dp = nxt

        if dp[n - 1][m - 1] > 0 and shortest_time == -1:
            shortest_time = _ + 1
        total_ways = (total_ways + dp[-1][-1]) % MOD
    if shortest_time == -1:
        print(-1)
    else:
        print(f"{total_ways} {shortest_time}")

先思考一种简单情况，没有检查官的时候，合法的方案数

定义dp[当前时刻][i][j]

当前时刻的单元格会从上方所有单元格和左边所有单元格转移过来，因此

dp[当前时刻][i][j]+=dp[上一时刻][i-1][j]+dp[上一时刻][i-2][j]....+dp[上一时刻][0][j]

dp[当前时刻][i][j]+=dp[上一时刻][i][j-1]+dp[上一时刻][i][j-2]....+dp[上一时刻][i][0]

可以依靠前缀和累计计算

dp[0][0][0]=1表示初始状态方案数为1

依次计算下一时刻状态

每计算完一次，累加最下方单元格值作为总方案数

再考虑有检察官的情况

通过vis记录当前位置是否有检察官

    for r, c in listener[_]:
        vis[r][c] = 1

当计算到有检察官的时候，将前缀和置为0，跳过当前单元格即可

            if vis[i][j]:
                prev = 0
                continue

最早的时刻可以通过记录右下单元格最早不为0的时刻，剩下的就是注意一些边界细节之类的