题解 | #旅行者的大逃脱#

题目链接

题目描述

在一个 $N \times M$ 的网格中，旅行者从左上角 $(1, 1)$ 出发，目标是到达右下角 $(N, M)$ 。初始时刻为 $0$ 。旅行者的移动规则如下：

每次移动，只能选择向下或向右，并且可以一次前进任意正整数步。
每完成一次移动，时刻（即移动次数）加 $1$ 。

有 $q$ 个检查官。第 $i$ 个检查官将在时刻 $t_i$ （即移动次数达到 $t_i$ 时）出现在格子 $(r_i, c_i)$ 并一直驻守。旅行者如果在第 $t$ 次移动时，其路径（包括起点和终点）接触到 $(r_i, c_i)$ 且 $t \ge t_i$ ，就会被捕获。大门在时刻 $k$ 后关闭，若到达 $(N, M)$ 时移动次数已经大于 $k$ ，也算失败。

你需要计算：

逃离所需的最短时间（最少移动次数）。
在所有合法方案中，可以逃脱的总方案数量（对 $998244353$ 取模）。如果无法逃脱，输出 $-1$ 。

解题思路

本题要求计算两个独立的值：一是能到达终点的最短时间（最少移动次数），二是所有能在时间限制 $k$ 内到达终点的方案总数。

我们可以使用动态规划来解决，并通过时间步（移动次数）进行迭代。由于当前时刻的状态只与上一时刻有关，我们可以使用滚动数组优化空间。

状态定义： $f[i][j]$ ：在当前时刻 $t$ 到达格子 $(i, j)$ 的方案数。

初始化： $f[0][0] = 1$ (使用0-indexed坐标)，表示在时刻 $0$ （移动 $0$ 次），位于起点的方案数为 $1$ 。

状态转移：我们迭代时刻 $t$ 从 $0$ 到 $k-1$ 。在每个时刻 $t$ ，我们根据 $t$ 时刻的状态 $f$ 计算出 $t+1$ 时刻的状态 $g$ 。 $g[i][j]$ 的值由两部分贡献：

从上方格子 $(x, j)$ (其中 $x < i$ ) 移动而来。
从左方格子 $(i, y)$ (其中 $y < j$ ) 移动而来。

转移优化 (前缀和)：朴素的转移需要遍历所有来源点，效率低下。我们可以使用前缀和来优化。

计算来自上方的贡献：遍历每一列 $j$ ，用一个变量 $pre$ 维护 $f[0 \dots i-1][j]$ 的方案数之和。在遍历 $i$ 时， $g[i][j]$ 直接加上 $pre$ 。 $pre$ 自身则累加 $f[i][j]$ 。
计算来自左方的贡献：同理，遍历每一行 $i$ ，用变量 $pre$ 维护 $f[i][0 \dots j-1]$ 的方案数之和，并更新 $g[i][j]$ 。

障碍处理：在每个时刻 $t$ (对应第 $t+1$ 次移动) 开始计算前：

将所有在时刻 $t$ 或之前出现的障碍物位置记录在 $vis$ 数组中。
对于恰好在时刻 $t$ 出现的障碍 $(r, c)$ ，执行 $f[r][c] = 0$ 。这代表在 $t-1$ 时刻到达 $(r, c)$ 的所有方案在时刻 $t$ 都无法从该点出发，因此这些方案数作废。
在计算前缀和时，若遇到任何已标记的障碍 ( $vis[i][j] == 1$ )，则将前缀和 $pre$ 清零，表示此路不通，无法跨越障碍。

算法流程：

初始化 $f[0][0] = 1$ 。初始化 $shortest\_time = -1$ ， $total\_ways = 0$ 。
外层循环 $t$ 从 $0$ 到 $k-1$ 。
在循环 $t$ 内部： a. 处理在时刻 $t$ 新出现的障碍，更新 $vis$ 数组，并执行 $f[r][c] = 0$ 。
b. 初始化下一时刻的状态数组 $g$ 为全 $0$ 。
c. 按行转移：使用前缀和计算所有从左方来的贡献，累加到 $g$ 中。
d. 按列转移：使用前缀和计算所有从上方来的贡献，累加到 $g$ 中。
e. 将 $g$ 的状态赋给 $f$ ，完成一次迭代。
f. 统计结果：
- 如果 $shortest\_time$ 仍为 $-1$ 且 $f[N-1][M-1] > 0$ ，说明这是第一次到达终点，记录 $shortest\_time = t + 1$ 。
- 将 $f[N-1][M-1]$ 累加到 $total\_ways$ 中。
循环结束后，根据 $shortest\_time$ 是否为 $-1$ 输出结果。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MOD = 998244353;

void solve() {
    int n, m, q, k;
    cin >> n >> m >> q >> k;
    vector<vector<pair<int, int>>> listener(k);
    for (int i = 0; i < q; ++i) {
        int r, c, t;
        cin >> r >> c >> t;
        if (t - 1 < k) {
            listener[t - 1].push_back({r - 1, c - 1});
        }
    }

    vector<vector<long long>> f(n, vector<long long>(m, 0));
    f[0][0] = 1;

    long long total_ways = 0;
    int shortest_time = -1;

    vector<vector<int>> vis(n, vector<int>(m, 0));

    for (int t = 0; t < k; ++t) {
        for (auto const& [r, c] : listener[t]) {
            vis[r][c] = 1;
            f[r][c] = 0; // 关键：在t时刻出现在(r,c)的障碍，会使t-1时刻到达(r,c)的方案作废
        }

        vector<vector<long long>> g(n, vector<long long>(m, 0));

        // 按行转移 (从左方来)
        for (int i = 0; i < n; ++i) {
            long long pre = 0;
            for (int j = 0; j < m; ++j) {
                if (vis[i][j]) {
                    pre = 0;
                }
                g[i][j] = (g[i][j] + pre) % MOD;
                pre = (pre + f[i][j]) % MOD;
            }
        }

        // 按列转移 (从上方来)
        for (int j = 0; j < m; ++j) {
            long long pre = 0;
            for (int i = 0; i < n; ++i) {
                if (vis[i][j]) {
                    pre = 0;
                }
                g[i][j] = (g[i][j] + pre) % MOD;
                pre = (pre + f[i][j]) % MOD;
            }
        }
        
        f = g;

        if (f[n - 1][m - 1] > 0 && shortest_time == -1) {
            shortest_time = t + 1;
        }
        total_ways = (total_ways + f[n - 1][m - 1]) % MOD;
    }

    if (shortest_time == -1) {
        cout << -1 << "\n";
    } else {
        cout << total_ways << " " << shortest_time << "\n";
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static final int MOD = 998244353;

    public static void solve(Scanner sc) {
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q = sc.nextInt();
        int k = sc.nextInt();

        List<List<int[]>> listener = new ArrayList<>(k);
        for (int i = 0; i < k; i++) {
            listener.add(new ArrayList<>());
        }
        for (int i = 0; i < q; i++) {
            int r = sc.nextInt();
            int c = sc.nextInt();
            int t = sc.nextInt();
            if (t - 1 < k) {
                listener.get(t - 1).add(new int[]{r - 1, c - 1});
            }
        }

        long[][] f = new long[n][m];
        f[0][0] = 1;

        long totalWays = 0;
        int shortestTime = -1;
        int[][] vis = new int[n][m];

        for (int t = 0; t < k; t++) {
            for (int[] pos : listener.get(t)) {
                vis[pos[0]][pos[1]] = 1;
                f[pos[0]][pos[1]] = 0; // 关键：作废方案
            }

            long[][] g = new long[n][m];

            // 按行转移 (从左方来)
            for (int i = 0; i < n; i++) {
                long pre = 0;
                for (int j = 0; j < m; j++) {
                    if (vis[i][j] == 1) {
                        pre = 0;
                    }
                    g[i][j] = (g[i][j] + pre) % MOD;
                    pre = (pre + f[i][j]) % MOD;
                }
            }
            
            // 按列转移 (从上方来)
            for (int j = 0; j < m; j++) {
                long pre = 0;
                for (int i = 0; i < n; i++) {
                    if (vis[i][j] == 1) {
                        pre = 0;
                    }
                    g[i][j] = (g[i][j] + pre) % MOD;
                    pre = (pre + f[i][j]) % MOD;
                }
            }

            f = g;

            if (f[n - 1][m - 1] > 0 && shortestTime == -1) {
                shortestTime = t + 1;
            }
            totalWays = (totalWays + f[n - 1][m - 1]) % MOD;
        }

        if (shortestTime == -1) {
            System.out.println(-1);
        } else {
            System.out.println(totalWays + " " + shortestTime);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }
}

MOD = 998244353

def solve():
    n, m, q, k = map(int, input().split())
    
    listener = [[] for _ in range(k)]
    for _ in range(q):
        r, c, t = map(int, input().split())
        if t - 1 < k:
            listener[t - 1].append((r - 1, c - 1))

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

    for t in range(k):
        # 标记当前时刻生效的障碍，并作废相关方案
        for r, c in listener[t]:
            vis[r][c] = 1
            f[r][c] = 0 # 关键点
        
        g = [[0] * m for _ in range(n)]
        
        # 按行转移 (从左方来)
        for i in range(n):
            pre = 0
            for j in range(m):
                if vis[i][j]:
                    pre = 0
                g[i][j] = (g[i][j] + pre) % MOD
                pre = (pre + f[i][j]) % MOD
        
        # 按列转移 (从上方来)
        for j in range(m):
            pre = 0
            for i in range(n):
                if vis[i][j]:
                    pre = 0
                g[i][j] = (g[i][j] + pre) % MOD
                pre = (pre + f[i][j]) % MOD

        f = g
        
        # 统计结果
        if f[n - 1][m - 1] > 0 and shortest_time == -1:
            shortest_time = t + 1
        total_ways = (total_ways + f[n - 1][m - 1]) % MOD

    if shortest_time == -1:
        print(-1)
    else:
        print(f"{total_ways} {shortest_time}")

def main():
    T_cases = int(input())
    for _ in range(T_cases):
        solve()

if __name__ == "__main__":
    main()

算法及复杂度

算法：动态规划（滚动数组 + 前缀和优化）
时间复杂度： $O(k \cdot N \cdot M)$ - 迭代 $k$ 次，每次迭代对 $N \cdot M$ 网格进行线性扫描。
空间复杂度： $O(N \cdot M + q)$ - 主要开销来自存储DP状态的滚动数组和检查官信息。