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

1. 问题分析

• 初始状态：时刻 1 旅行者位于 (1,1)，对应 dp[1][1] = 1。
• 移动代价：在时刻 发起跳跃，到达目标格子的时刻为 。
• 路径安全性：
  • 跳跃瞬间（时刻 ）：从起点到终点路径上的所有格子必须满足 。
  • 落脚瞬间（时刻 ）：目标格子必须满足 。
• 最大限制：总时刻 。

2. 转移推导

利用前缀和优化 的区间跳跃： 其中：

• 垂直贡献 =
• 水平贡献 = 和 分别是该行/列在当前时刻 遭遇的最靠近的障碍物坐标。

3. C++ 代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static constexpr ll MOD = 998244353;

static std::array<std::array<ll, 505>, 505> dp_curr, dp_next;
static std::array<std::array<ll, 505>, 505> Sv, Sh;
static std::array<std::array<int, 505>, 505> P;
static std::array<int, 505> up_limit;

void solve() {
    int n, m, q, k;
    if (!(cin >> n >> m >> q >> k)) return;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            P[i][j] = k + 1;
            dp_curr[i][j] = 0;
        }
    }

    for (int i = 0; i < q; i++) {
        int x, y, t;
        cin >> x >> y >> t;
        if (x <= n && y <= m) P[x][y] = min(P[x][y], t);
    }

    // 初始化：时刻 1 在 (1,1)
    dp_curr[1][1] = 1;

    ll total_ans = 0;
    int shortest_time = -1;

    for (int t = 1; t <= k; t++) {
        // 1. 统计当前时刻到达终点的方案
        if (dp_curr[n][m] > 0) {
            if (shortest_time == -1) shortest_time = t;
            total_ans = (total_ans + dp_curr[n][m]) % MOD;
        }

        // 如果达到最大时刻 k，不再向后转移
        if (t == k) break;

        // 2. 预处理当前时刻的前缀和
        // 如果 P[i][j] <= t，说明此刻该位置有障碍，方案数失效（离开被捕）
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                ll val = (P[i][j] > t) ? dp_curr[i][j] : 0;
                Sv[i][j] = (Sv[i - 1][j] + val) % MOD;
                Sh[i][j] = (Sh[i][j - 1] + val) % MOD;
                dp_next[i][j] = 0; // 清空下一时刻
            }
        }

        // 3. 转移计算 t+1 时刻的状态
        up_limit.fill(0);
        for (int i = 1; i <= n; i++) {
            int left_limit = 0;
            for (int j = 1; j <= m; j++) {
                // 如果 P[i][j] <= t，说明时刻 t 该路径被切断（经过被捕）
                if (P[i][j] <= t) {
                    up_limit[j] = i;
                    left_limit = j;
                }

                // 目标格子在到达时刻 t+1 必须安全（到达被捕）
                if (P[i][j] <= t + 1) {
                    dp_next[i][j] = 0;
                } else {
                    ll v_sum = (Sv[i - 1][j] - Sv[up_limit[j]][j] + MOD) % MOD;
                    ll h_sum = (Sh[i][j - 1] - Sh[i][left_limit] + MOD) % MOD;
                    dp_next[i][j] = (v_sum + h_sum) % MOD;
                }
            }
        }
        // 滚动数组交换
        dp_curr = dp_next;
    }

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if (cin >> T) {
        while (T--) solve();
    }
    return 0;
}

4. 复杂度分析

• 时间复杂度：。通过前缀和将每次转移从 降到 ，总计算次数约为 ，符合 2s 时限。
• 空间复杂度：。显式的滚动数组设计，内存占用约 10MB 左右，远低于题目限制。