题解 | #收集金币#

题目链接

收集金币

题目描述

在一个 $N \times M$ 的网格迷宫中，每个方格 $(r, c)$ 都有一定数量的金币。小K从左上角 $(1, 1)$ 出发，每回合只能向右或向下移动一格。

迷宫中存在动态障碍：已知有 $K$ 条信息，每条信息形如 $(r_i, c_i, t_i)$ ，表示方格 $(r_i, c_i)$ 会在第 $t_i$ 回合开始时永久变成墙。

小K的目标是规划一条路径，使得收集到的金币总数最多。一个方格中的金币只能被收集一次。

解题思路

这是一个带有时间限制的路径规划问题，是经典网格动态规划的变种。

1. 关键点：回合数与坐标的关系

小K从 $(1, 1)$ 出发，每回合移动一格。要想到达方格 $(r, c)$ ，必须经过 $(r-1)$ 次向下移动和 $(c-1)$ 次向右移动，总共移动 $(r-1) + (c-1)$ 次。

这意味着，小K 到达方格 $(r, c)$ 的时刻（即完成的移动回合数）恰好是 $r+c-2$ 。例如，到达 $(1, 2)$ 需要1回合，即 $1+2-2=1$ ；到达 $(2, 2)$ 需要2回合，即 $2+2-2=2$ 。

一个方格 $(r, c)$ 在第 $t$ 回合会变成墙。因此，小K必须在第 $t$ 回合之前到达该方格，即到达时间 $r+c-2$ 必须小于 $t$ 。

可通行条件：小K能进入方格 $(r, c)$ 的充要条件是 $r+c-2 < t_{(r,c)}$ ，其中 $t_{(r,c)}$ 是该方格变成墙的回合数（如果永不变成墙，则 $t_{(r,c)}$ 为无穷大）。

2. 动态规划设计

状态定义: $dp[i][j]$ 表示从起点 $(1, 1)$ 出发，到达方格 $(i, j)$ 时能收集到的最多金币数。
状态转移: 由于只能向右或向下移动，要到达 $(i, j)$ ，只能从上方 $(i-1, j)$ 或左方 $(i, j-1)$ 转移而来。因此，状态转移方程为： $dp[i][j] = \max(dp[i-1][j], dp[i][j-1]) + \text{coins}[i][j]$
约束条件: 在计算 $dp[i][j]$ 之前，我们必须首先检查方格 $(i, j)$ 是否可通行。
1. 如果 $i+j-2 \ge t_{(i,j)}$ ，则该方格无法到达， $dp[i][j]$ 应设为一个特殊值（如-1），表示不可达。
2. 在进行状态转移时，如果来源方格（如 $dp[i-1][j]$ ）的值为不可达，则不能从该方向转移。
基本情况:
- 起点 $(1, 1)$ 的到达时间为 $1+1-2=0$ 。题目保证信息中的 $t_i \ge 1$ ，且特别说明即使起点在第一回合变墙也不受影响。因此，起点 $(1, 1)$ 总是可以到达的。
- $dp[1][1] = \text{coins}[1][1]$ 。
最终答案: 题目没有指定终点，小K的路径可以在任何一个可达的方格结束。因此，最终的答案是整个 $dp$ 表中的最大值。

3. 实现细节

预处理墙信息：为了方便查询，我们可以用一个二维数组 wall_time[N+1][M+1] 来存储每个方格变墙的时间，初始值设为一个很大的数。
DP表初始化：可以将 dp 表初始化为一个负数，表示除起点外均不可达。
遍历顺序：从上到下、从左到右遍历网格，计算每个位置的 dp 值。

代码实现

c++
java
python

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

using namespace std;

const long long INF = 1e18;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> coins(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> coins[i][j];
        }
    }

    int k;
    cin >> k;
    vector<vector<int>> wall_time(n + 1, vector<int>(m + 1, 1e9));
    for (int i = 0; i < k; ++i) {
        int r, c, t;
        cin >> r >> c >> t;
        wall_time[r][c] = t;
    }

    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, -INF));

    // Base case: (1, 1)
    dp[1][1] = coins[1][1];

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (i == 1 && j == 1) continue;

            // 检查当前格子是否可达
            int arrival_time = i + j - 2;
            if (arrival_time >= wall_time[i][j]) {
                continue; // 此格子无法进入
            }

            long long from_up = -INF;
            if (i > 1 && dp[i - 1][j] != -INF) {
                from_up = dp[i - 1][j];
            }

            long long from_left = -INF;
            if (j > 1 && dp[i][j - 1] != -INF) {
                from_left = dp[i][j - 1];
            }

            long long prev_max = max(from_up, from_left);
            if (prev_max != -INF) {
                dp[i][j] = prev_max + coins[i][j];
            }
        }
    }

    long long max_coins = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            max_coins = max(max_coins, dp[i][j]);
        }
    }

    cout << max_coins << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        int[][] coins = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                coins[i][j] = sc.nextInt();
            }
        }

        int k = sc.nextInt();
        int[][] wallTime = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(wallTime[i], Integer.MAX_VALUE);
        }
        for (int i = 0; i < k; i++) {
            int r = sc.nextInt();
            int c = sc.nextInt();
            int t = sc.nextInt();
            wallTime[r][c] = t;
        }

        long[][] dp = new long[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dp[i], Long.MIN_VALUE);
        }

        // Base case: (1, 1)
        dp[1][1] = coins[1][1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (i == 1 && j == 1) continue;
                
                int arrivalTime = i + j - 2;
                if (arrivalTime >= wallTime[i][j]) {
                    continue; 
                }

                long fromUp = Long.MIN_VALUE;
                if (i > 1 && dp[i - 1][j] != Long.MIN_VALUE) {
                    fromUp = dp[i - 1][j];
                }

                long fromLeft = Long.MIN_VALUE;
                if (j > 1 && dp[i][j - 1] != Long.MIN_VALUE) {
                    fromLeft = dp[i][j - 1];
                }

                long prevMax = Math.max(fromUp, fromLeft);
                if (prevMax != Long.MIN_VALUE) {
                    dp[i][j] = prevMax + coins[i][j];
                }
            }
        }

        long maxCoins = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                maxCoins = Math.max(maxCoins, dp[i][j]);
            }
        }

        System.out.println(maxCoins);
    }
}

import sys

def main():
    try:
        n, m = map(int, sys.stdin.readline().split())
        coins = [[0] * (m + 1) for _ in range(n + 1)]
        for i in range(1, n + 1):
            row = list(map(int, sys.stdin.readline().split()))
            for j in range(1, m + 1):
                coins[i][j] = row[j - 1]

        k = int(sys.stdin.readline())
        wall_time = [[float('inf')] * (m + 1) for _ in range(n + 1)]
        for _ in range(k):
            r, c, t = map(int, sys.stdin.readline().split())
            wall_time[r][c] = t
            
    except (IOError, ValueError):
        return

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

    # Base case: (1, 1)
    dp[1][1] = coins[1][1]

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if i == 1 and j == 1:
                continue

            arrival_time = i + j - 2
            if arrival_time >= wall_time[i][j]:
                continue
            
            from_up = -1
            if i > 1 and dp[i - 1][j] != -1:
                from_up = dp[i - 1][j]
                
            from_left = -1
            if j > 1 and dp[i][j - 1] != -1:
                from_left = dp[i][j - 1]
                
            prev_max = max(from_up, from_left)
            if prev_max != -1:
                dp[i][j] = prev_max + coins[i][j]

    max_coins = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            max_coins = max(max_coins, dp[i][j])
            
    print(max_coins)


if __name__ == "__main__":
    main()

算法及复杂度

算法: 动态规划 (DP)
时间复杂度: $O(N \cdot M)$ 。我们需要遍历整个 $N \times M$ 的网格一次来填充DP表。预处理墙的信息需要 $O(K)$ 。因此总时间复杂度为 $O(N \cdot M + K)$ 。
空间复杂度: $O(N \cdot M)$ 。主要开销是存储金币网格、墙时间网格以及DP表。