UVA 12130 Summits - BFS + 貪心統計峰頂數量

問題描述

給定 h × w 的高度地圖，參數 d。一個格子是峰頂，當且僅當：從該格子出發，無法到達高度 ≤ (該峰頂高度 - d) 的格子，且無法到達更高的峰頂。求峰頂總數。

貪心 + BFS 策略

將所有格子按高度降序放入優先隊列。每次取出最高的未訪問格子 (x,y)，以其高度 H 為限進行 BFS：只能走到高度 > H - d 的格子。BFS 過程中記錄：

• 當前連通塊中高度等於 H 的格子數 cnt。
• 是否遇到高度 > H 的格子（標記 flag = false）。

正確性

按高度從高到低處理，保證先處理更高的峰頂。若一個連通塊能到達更高點，則它屬於那個更高峰頂的「勢力範圍」，不應單獨計數。每個格子只進隊一次，總複雜度 O(hw log(hw))。

參考代碼 (C++)

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int N = 505;
const int D[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int h, w, d, g[N][N], vis[N][N];

struct Point { int x, y, val; 
    Point(int x=0,int y=0,int v=0):x(x),y(y),val(v){}
    bool operator<(const Point& o) const { return val < o.val; }
};
priority_queue<Point> pq;

int bfs(int sx, int sy, int H) {
    queue<Point> q;
    q.push({sx, sy});
    vis[sx][sy] = H;
    int cnt = 1, flag = 1;
    while (!q.empty()) {
        Point u = q.front(); q.pop();
        for (int i = 0; i < 4; ++i) {
            int nx = u.x + D[i][0], ny = u.y + D[i][1];
            if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
            if (H - g[nx][ny] >= d) continue;          // 太低
            if (vis[nx][ny] > H) { flag = 0; continue; } // 能到更高峰
            if (vis[nx][ny] == H) continue;
            if (g[nx][ny] == H) ++cnt;
            vis[nx][ny] = H;
            q.push({nx, ny});
        }
    }
    return flag ? cnt : 0;
}

int solve() {
    memset(vis, -1, sizeof(vis));
    int ans = 0;
    while (!pq.empty()) {
        Point u = pq.top(); pq.pop();
        if (vis[u.x][u.y] != -1) continue;
        ans += bfs(u.x, u.y, g[u.x][u.y]);
    }
    return ans;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &h, &w, &d);
        for (int i = 0; i < h; ++i)
            for (int j = 0; j < w; ++j) {
                scanf("%d", &g[i][j]);
                pq.push({i, j, g[i][j]});
            }
        printf("%d\n", solve());
    }
    return 0;
}