「PA 2020」Wycieczka górska 题解

算法思路

本题使用BFS最短路径和数学分析来解决登山比赛问题。核心观察是虽然每个旅行者的速度不同，但最优路径的结构是固定的，可以通过数学公式计算每个人的时间。

关键观察

1. 地形特性

• 只能向右或向下移动（向更高区域）
• 只能向左或向上移动（向更低区域）
• 危险区域不能通过

2. 路径结构分析

从 $(1,1)$ 到 $(n,m)$ 的最短路径：

• 必须向右移动 $m-1$ 次
• 必须向下移动 $n-1$ 次
• 总移动次数：$D = d[n][m]$

代码解析

BFS计算最短路径

queue<pair<int, int>> q;
memset(d, -1, sizeof(d));
q.push({1, 1});
d[1][1] = 0;

while (!q.empty()) {
    auto [x, y] = q.front();
    q.pop();
    
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        
        if (nx < 1 || nx > n || ny < 1 || ny > m || 
            s[nx][ny] == 'X' || d[nx][ny] != -1)
            continue;
            
        d[nx][ny] = d[x][y] + 1;
        q.push({nx, ny});
    }
}

路径分解计算

int D = d[n][m];
int A = (D - (n + m - 2)) / 2 + n + m - 2, B = D - A;

数学推导：

• 最小曼哈顿距离：$(n-1) + (m-1) = n + m - 2$
• 额外移动次数：$D - (n + m - 2)$
• 由于地形约束，额外移动中一半是向高，一半是向低
• 因此：
  • 向高移动次数：$A = \frac{D - (n + m - 2)}{2} + (n + m - 2)$
  • 向低移动次数：$B = D - A$

计算每个旅行者时间

pair<int, int> ans = {1e18, 0};
while (k--) {
    int a, b;
    cin >> a >> b;
    int w = a * A + b * B;  // 总时间 = a×向高次数 + b×向低次数
    
    if (w < ans.first)
        ans = {w, 1};
    else if (w == ans.first)
        ans.second++;
}

算法正确性

路径特性证明

由于地形单调性（右/下为高，左/上为低），从起点到终点的最优路径中：

• 必须的向高移动：$n-1$ 次向下 + $m-1$ 次向右
• 额外的移动必然成对出现（一次向高对应一次向低）

时间复杂度分析

• BFS：$O(nm)$
• 处理旅行者：$O(k)$
• 总复杂度：$O(nm + k)$

关键技巧

1. BFS求最短路径：在网格图中找到避开危险区域的最短路径
2. 路径分解：将总路径分解为向高和向低移动次数
3. 数学优化：避免为每个旅行者重新计算路径