题目描述

一个印第安部落经过长途跋涉，在北美山区找到了一个新的定居点。由于地形崎岖，帐篷之间的海拔差异会导致行走困难。部落酋长要求他的儿子“快思”找到一个连通区域，能够容纳所有帐篷，且该区域内最高点与最低点的海拔差尽可能小。

快思将土地划分为 $r\times c$ 的网格（$r,c\le 40$），每个格子有一个海拔高度 $a_{i,j}$（$0\le a_{i,j}\le 99$）。两个格子是相邻的当它们共享一条边（四连通）。一个区域是连通的，如果区域内任意两个格子之间存在一条由相邻格子组成的路径。

给定 $n$ 个查询（$n\le 100$），对于每个查询 $k_i$（$k_i\le r\times c$），需要找到至少包含 $k_i$ 个格子的连通区域，使得区域内最高海拔与最低海拔的差值最小。

输入格式

• 第一行：两个整数 $r,c$
• 接下来 $r$ 行：每行 $c$个 整数，表示海拔矩阵
• 接下来一行：整数 $n$
• 接下来 $n$ 行：每行一个整数 $k_i$

输出格式

对于每个$k_i$，输出一行，表示最小可能的海拔差。

样例分析

样例输入：

5 10
0 0 3 46 0 46 0 0 12 12
0 0 13 50 49 46 11 10 10 11
0 51 51 49 99 99 89 0 0 10
0 0 48 82 70 99 0 52 13 14
51 50 50 51 70 35 70 10 14 11
6
1
5
10
12
47
50

样例输出：

0
0
3
4
89
99

题目分析

问题本质

这是一个在二维网格中寻找连通子区域的问题，需要满足：

1. 区域包含至少 $k$ 个格子
2. 区域内海拔值的极差（最大值减最小值）最小

这是一个组合优化问题，我们需要在指数级的可能区域中寻找最优解。

关键观察

1. 高度范围有限：海拔高度仅在 $0$ 到 $99$ 之间，只有 $100$ 种可能值
2. 极差最小化：最优解的高度范围一定是一个连续区间 $[low,high]$，其中 $low$ 和 $high$ 都是矩阵中实际存在的海拔值
3. 连通性约束：需要在指定高度范围内的格子中找到足够大的连通块

解题思路

核心思想：枚举+验证

由于高度值范围很小（仅 $100$ 种可能），我们可以采用枚举高度区间的方法：

1. 枚举下界 $low$：遍历所有在矩阵中实际出现的海拔值
2. 确定上界 $high$：对于给定的极差 $diff$，$high=low+diff$
3. 验证可行性：检查在高度范围 $[low,high]$ 内，是否存在大小至少为 $k$ 的连通块

算法框架

对于每个查询 $k$：

1. 如果 $k=1$，答案为 $0$（单个格子的极差为 $0$）
2. 收集所有不同的海拔值并排序
3. 对于每个可能的下界 $low$，使用二分查找找到最小的 $diff$ 使得存在满足条件的区域
4. 取所有 $low$ 对应的最小 $diff$ 中的最小值作为答案

验证函数设计

对于给定的 $low$ 和 $high$：

1. 标记所有海拔在 $[low,high]$ 范围内的格子
2. 如果标记的格子总数小于 $k$，直接返回 false
3. 使用 $\text{BFS}$ 或 $\text{DFS}$ 遍历所有标记的格子，寻找最大的连通块
4. 如果最大连通块大小 $\ge k$，返回 true；否则返回 false

时间复杂度分析

• 矩阵大小：最多 $40\times 40=1600$ 个格子
• 不同高度值：最多 $100$个
• 对于每个 $low$：二分查找最多 ${\log }_{2}100\approx 7$ 次
• 每次验证：$\text{BFS}$ 遍历最多 $1600$ 个格子

总时间复杂度约为：$O(100\times 7\times 1600)\approx 1.1\times 10^6$ 次操作，完全可行。

优化技巧

1. 预处理高度值：只考虑实际出现的海拔值，减少枚举量
2. 提前剪枝：如果高度范围内的格子总数不足$k$，直接跳过
3. 使用$\text{BFS}$：避免递归深度过大，提高效率
4. 复用标记数组：使用同一个数组标记"是否在高度范围内"和"是否已访问"

算法实现细节

数据结构

• altitude[MAX][MAX]：存储海拔矩阵
• inRange[MAX][MAX]：标记格子是否在当前高度范围内且未访问
• heights：存储所有不同的海拔值

关键函数

$\text{bfs}$ 函数

执行广度优先搜索，统计连通块大小。使用队列实现，避免递归。

$\text{checkRange}$ 函数

检查在高度范围 $[minH,maxH]$ 内是否存在大小至少为 $k$ 的连通块：

1. 标记所有在范围内的格子
2. 如果总数不足 $k$，直接返回 false
3. 遍历所有在范围内的格子，进行 $\text{BFS}$ 统计连通块大小
4. 一旦找到大小 $\ge k$ 的连通块，立即返回 true

主逻辑

对于每个查询 $k$：

1. 特判 $k=1$ 的情况
2. 遍历所有可能的下界 $low$
3. 对每个 $low$，二分查找最小 $diff$
4. 取所有结果的最小值

代码实现

// Mountain Village
// UVa ID: 10486
// Verdict: Accepted
// Submission Date: 2025-12-02
// UVa Run Time: 0.020s
//
// 版权所有（C）2025，邱秋。metaphysis # yeah dot net

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

const int MAX = 45;

int r, c;
int altitude[MAX][MAX];
bool inRange[MAX][MAX];
int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

// BFS统计连通块大小
int bfs(int startRow, int startCol) {
    if (!inRange[startRow][startCol]) return 0;
    queue<pair<int, int>> q;
    q.push({startRow, startCol});
    inRange[startRow][startCol] = false; // 标记为已访问
    int cnt = 0;
    
    while (!q.empty()) {
        auto [row, col] = q.front(); q.pop();
        cnt++;
        
        for (int i = 0; i < 4; ++i) {
            int nr = row + dirs[i][0];
            int nc = col + dirs[i][1];
            if (nr >= 1 && nr <= r && nc >= 1 && nc <= c && inRange[nr][nc]) {
                inRange[nr][nc] = false;
                q.push({nr, nc});
            }
        }
    }
    return cnt;
}

// 检查是否存在高度范围在[minH, maxH]内的连通块，其大小至少为k
bool checkRange(int minH, int maxH, int k) {
    // 标记所有在高度范围内的格子
    int totalInRange = 0;
    for (int i = 1; i <= r; ++i) {
        for (int j = 1; j <= c; ++j) {
            inRange[i][j] = (altitude[i][j] >= minH && altitude[i][j] <= maxH);
            if (inRange[i][j]) totalInRange++;
        }
    }
    
    // 如果总数都不够k，直接返回false
    if (totalInRange < k) return false;
    
    // 寻找最大的连通块
    for (int i = 1; i <= r; ++i) {
        for (int j = 1; j <= c; ++j) {
            if (inRange[i][j]) {
                int size = bfs(i, j);
                if (size >= k) return true;
            }
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> r >> c;
    vector<int> heights;
    for (int i = 1; i <= r; ++i) {
        for (int j = 1; j <= c; ++j) {
            cin >> altitude[i][j];
            heights.push_back(altitude[i][j]);
        }
    }
    
    // 去重并排序所有高度值
    sort(heights.begin(), heights.end());
    heights.erase(unique(heights.begin(), heights.end()), heights.end());
    
    int n;
    cin >> n;
    
    while (n--) {
        int k;
        cin >> k;
        
        if (k == 1) { // 特殊情况处理
            cout << 0 << '\n';
            continue;
        }
        
        int ans = 100; // 最大可能高度差
        int hCount = heights.size();
        
        // 枚举所有可能的高度范围
        for (int i = 0; i < hCount; ++i) {
            int low = heights[i];
            // 二分查找满足条件的最小高度差
            int left = 0, right = 99 - low;
            int bestForLow = 100;
            
            while (left <= right) {
                int mid = (left + right) / 2;
                int high = low + mid;
                
                // 查找heights中不超过high的最大值
                auto it = upper_bound(heights.begin(), heights.end(), high);
                if (it == heights.begin()) {
                    left = mid + 1;
                    continue;
                }
                int actualHigh = *prev(it);
                
                if (checkRange(low, actualHigh, k)) {
                    bestForLow = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            
            ans = min(ans, bestForLow);
        }
        
        cout << ans << '\n';
    }
    
    return 0;
}

总结

本题的关键在于利用高度值范围小的特点，通过枚举高度区间将问题转化为连通块大小检查。主要算法步骤：

1. 收集所有不同的海拔值
2. 枚举下界高度 $low$
3. 二分查找最小高度差 $diff$
4. 验证在 $[low,low+diff]$ 范围内是否存在足够大的连通块

通过合理的剪枝和优化，算法能够在时间限制内解决问题。这个解题思路也展示了如何将复杂的二维区域选择问题转化为可管理的枚举验证问题。