题解 | #收集金币#

题目链接

题目描述

在一个 $R \times C$ 的网格迷宫中，每个方格 $(i, j)$ 都有一定数量的金币。小K从左上角 $(1, 1)$ 出发，每回合只能向右或向下移动一格。有 $K$ 条信息，每条信息表示方格 $(r, c)$ 会在第 $t$ 回合变成永久的墙。小K在第 $t$ 回合移动时，会先等所有该回合的墙出现后，再进行移动决策。你需要计算小K最多能收集到多少金币。

输入:

第一行输入 $R, C$ 。
接下来 $R$ 行，每行 $C$ 个整数，表示每个方格的金币数。
接下来一行输入一个整数 $K$ 。
接下来 $K$ 行，每行三个整数 $r, c, t$ ，表示一条信息。

输出:

输出一个整数，代表小K最多能收集到的金币数量。

解题思路

这是一个在带有动态障碍的网格上求最大收益路径的问题。问题的关键在于正确计算小K到达每个格子的回合数，从而判断该格子是否可达。

时间与位置的关系:
- 小K从 $(1, 1)$ 出发，只能向右或向下移动。要到达方格 $(i, j)$ ，他必须走 $(i-1)$ 步向下和 $(j-1)$ 步向右，总共需要走 $(i-1) + (j-1)$ 步。
- 每次移动消耗一个回合，因此，进入方格 $(i, j)$ 的那次移动发生在第 t = (i-1) + (j-1) 回合。
判断格子是否可达:
- 根据题目“每回合开始时，方格先发生变化，小K再进行移动”，当小K在第 $t$ 回合准备移动时，所有标记为第 $t$ 回合或更早的墙都已经出现了。
- 因此，一个方格 $(i, j)$ 是可通行的，当且仅当它的建墙时间 wall_time[i][j] 严格大于 小K到达它的回合数 (i-1) + (j-1)。
- 这个判断逻辑也自然地处理了起点的特殊情况：对于 $(1, 1)$ ，到达回合为0。任何墙的建立时间 $t \ge 1$ ，所以 wall_time[1][1] > 0 恒成立，起点永远可达。
动态规划:
- 状态定义: $dp[i][j]$ 表示从起点 $(1, 1)$ 出发，到达方格 $(i, j)$ 时能收集到的最大金币数。
- 状态转移:
  - 状态转移方程为： $dp[i][j] = \max(dp[i-1][j], dp[i][j-1]) + \text{coins}[i][j]$ 。
  - 这个转移只有在 $(i, j)$ 可通行，并且来源格子 $(i-1, j)$ 或 $(i, j-1)$ 可达（其DP值有效）时才发生。
- 遍历顺序: 我们可以从上到下、从左到右遍历整个网格，依次计算每个格子的DP值。

最终，所有可达格子 $(i, j)$ 的 $dp[i][j]$ 值中的最大值，就是小K能收集到的最多金币数。

代码

c++
java
python

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

using namespace std;

const long long INVALID = -1;

int main() {
    int R, C;
    cin >> R >> C;

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

    int K;
    cin >> K;
    vector<vector<int>> wall_time(R + 1, vector<int>(C + 1, 1e9 + 7));
    for (int i = 0; i < K; ++i) {
        int r, c, t;
        cin >> r >> c >> t;
        wall_time[r][c] = min(wall_time[r][c], t);
    }
    
    vector<vector<long long>> dp(R + 1, vector<long long>(C + 1, INVALID));
    
    for (int i = 1; i <= R; ++i) {
        for (int j = 1; j <= C; ++j) {
            int arrival_round = (i - 1) + (j - 1);
            if (wall_time[i][j] <= arrival_round) {
                continue; // 此格在到达时已是墙
            }

            if (i == 1 && j == 1) {
                dp[i][j] = coins[i][j];
                continue;
            }
            
            long long from_top = (i > 1) ? dp[i - 1][j] : INVALID;
            long long from_left = (j > 1) ? dp[i][j - 1] : INVALID;

            if (from_top == INVALID && from_left == INVALID) {
                continue; // 无法从任何有效路径到达此格
            }
            
            dp[i][j] = max(from_top, from_left) + coins[i][j];
        }
    }

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

    cout << max_coins << "\n";
    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 R = sc.nextInt();
        int C = sc.nextInt();

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

        int K = sc.nextInt();
        int[][] wallTime = new int[R + 1][C + 1];
        for (int[] row : wallTime) {
            Arrays.fill(row, 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] = Math.min(wallTime[r][c], t);
        }

        long[][] dp = new long[R + 1][C + 1];
        for (long[] row : dp) {
            Arrays.fill(row, -1);
        }
        
        for (int i = 1; i <= R; i++) {
            for (int j = 1; j <= C; j++) {
                int arrivalRound = (i - 1) + (j - 1);
                if (wallTime[i][j] <= arrivalRound) {
                    continue; // 此格在到达时已是墙
                }

                if (i == 1 && j == 1) {
                    dp[i][j] = coins[i][j];
                    continue;
                }

                long fromTop = (i > 1) ? dp[i - 1][j] : -1;
                long fromLeft = (j > 1) ? dp[i][j - 1] : -1;

                if (fromTop == -1 && fromLeft == -1) {
                    continue; // 无法从任何有效路径到达此格
                }
                
                dp[i][j] = Math.max(fromTop, fromLeft) + coins[i][j];
            }
        }

        long maxCoins = 0;
        for (int i = 1; i <= R; i++) {
            for (int j = 1; j <= C; j++) {
                maxCoins = Math.max(maxCoins, dp[i][j]);
            }
        }
        System.out.println(maxCoins);
    }
}

# 读取输入
R, C = map(int, input().split())
coins = []
for _ in range(R):
    coins.append(list(map(int, input().split())))

K = int(input())
wall_time = {}
for _ in range(K):
    r, c, t = map(int, input().split())
    # 记录每个格子最早变成墙的时间
    if (r, c) not in wall_time or t < wall_time[(r, c)]:
        wall_time[(r, c)] = t

# dp[i][j] 表示到达 (i, j) 的最大金币数 (0-indexed)
dp = [[-1] * C for _ in range(R)]

for i in range(R):
    for j in range(C):
        arrival_round = i + j
        # 如果当前格子在到达时已是墙，则不可达
        if wall_time.get((i + 1, j + 1), float('inf')) <= arrival_round:
            continue
        
        if i == 0 and j == 0:
            dp[i][j] = coins[i][j]
            continue

        from_top = dp[i - 1][j] if i > 0 else -1
        from_left = dp[i][j - 1] if j > 0 else -1
        
        if from_top == -1 and from_left == -1:
            continue
            
        dp[i][j] = max(from_top, from_left) + coins[i][j]


max_coins = 0
for i in range(R):
    for j in range(C):
        max_coins = max(max_coins, dp[i][j])

print(max_coins)

算法及复杂度

算法：动态规划
时间复杂度： $O(R \cdot C)$ - 我们需要遍历整个网格一次来计算所有格子的DP值。
空间复杂度： $O(R \cdot C)$ - 主要开销来自存储金币、墙体信息和DP状态的二维数组。