Thin Ice 题解

题目分析

Uolevi 在一个 $n \times m$ 的网格冰面上移动，每个格子：

• 初始有 1 枚硬币
• 有耐久度 $d$，表示该格子能承受的最大硬币数（包括Uolevi携带的硬币）

约束条件：

• 起点和终点必须是边缘格子（第一行/最后一行/第一列/最后一列）
• 移动时，当前格子的硬币总数（地上的 + Uolevi携带的）不能超过耐久度
• Uolevi可以捡起所在格子的硬币

目标：最大化收集的硬币数量。

关键观察

1. 耐久度约束的本质：当Uolevi携带 $c$ 枚硬币进入耐久度为 $d$ 的格子时，必须满足 $c + 1 \leq d$（因为地上还有1枚硬币）。

2. 状态设计：我们需要记录 (位置, 携带硬币数) 的状态，表示在某个位置携带特定数量硬币是否可达。

3. 起点选择：由于起点必须是边缘格子且初始携带0枚硬币，我们可以从所有边缘格子开始BFS。

4. 答案计算：最终答案是所有边缘格子中，可达状态的最大携带硬币数。

算法思路

状态表示

• 状态：(x, y, coins) 表示在位置 (x,y) 携带 coins 枚硬币
• 初始状态：所有边缘格子 (x,y,0)，其中 (x,y) 是边缘位置
• 目标：找到所有边缘格子可达状态中的最大 coins 值

状态转移

从状态 (x, y, c) 可以转移到相邻格子 (nx, ny)：

• 如果 c + 1 <= d[nx][ny]，则可以捡起新硬币：(nx, ny, c+1)
• 如果 c <= d[nx][ny]，则可以不捡硬币：(nx, ny, c)

算法步骤

1. 初始化队列，将所有边缘格子的 (x,y,0) 状态入队
2. 使用BFS/Dijkstra遍历所有可达状态
3. 记录每个位置能达到的最大硬币数
4. 最终检查所有边缘位置能达到的最大硬币数

复杂度分析

• 状态数：$O(nm \cdot D)$，其中 $D$ 是最大耐久度
• 每个状态最多扩展4个邻居
• 总复杂度：$O(nm \cdot D)$

对于 $nm \leq 2\times 10^5$ 且 $D \leq 2\times 10^5$ 的数据，需要优化。

优化策略

实际上，对于每个位置 (x,y)，我们只关心能达到的最大硬币数。因此可以优化：

• 对于每个位置，记录 maxCoins[x][y] 表示在该位置能达到的最大硬币数
• 使用优先队列，优先扩展硬币数多的状态（类似Dijkstra）
• 这样每个位置只需要被访问一次

代码实现

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

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> d(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> d[i][j];
        }
    }
    
    vector<vector<int>> maxCoins(n, vector<int>(m, -1));
    priority_queue<tuple<int, int, int>> pq; // (coins, x, y)
    
    // 初始化边缘格子
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i == 0 || i == n-1 || j == 0 || j == m-1) {
                if (d[i][j] >= 1) { // 可以捡起硬币
                    maxCoins[i][j] = 1;
                    pq.push({1, i, j});
                }
            }
        }
    }
    
    // BFS with priority queue
    while (!pq.empty()) {
        auto [coins, x, y] = pq.top();
        pq.pop();
        
        if (coins < maxCoins[x][y]) continue;
        
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            
            // 尝试携带当前硬币数进入新格子（不捡新硬币）
            if (coins <= d[nx][ny]) {
                if (coins > maxCoins[nx][ny]) {
                    maxCoins[nx][ny] = coins;
                    pq.push({coins, nx, ny});
                }
            }
            
            // 尝试携带当前硬币数+1进入新格子（捡新硬币）
            if (coins + 1 <= d[nx][ny]) {
                if (coins + 1 > maxCoins[nx][ny]) {
                    maxCoins[nx][ny] = coins + 1;
                    pq.push({coins + 1, nx, ny});
                }
            }
        }
    }
    
    // 找边缘格子的最大硬币数
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if ((i == 0 || i == n-1 || j == 0 || j == m-1) && maxCoins[i][j] > ans) {
                ans = maxCoins[i][j];
            }
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

样例解释

对于样例：

3 4
1 1 1 1
1 3 6 1
3 4 5 1

最优路径：从左上角(0,0)开始，按照下→右→下→左→右→右的路径，可以收集5枚硬币。无法收集6枚，因为会受到耐久度限制无法回到边缘。

总结

本题的关键在于将物理约束转化为图论问题，通过状态设计和优先队列优化来求解。难点在于理解耐久度约束对状态转移的影响，以及如何高效地遍历所有可能的状态。