UVA 12130 Summits：BFS 尋找地形峰值點

問題描述

給定 N×M 網格，每個格子有高度值。從高度 G 的格子出發，只能移動到高度差 < D 的相鄰格子。峰值點定義為：無法移動到比自己更高的格子。求所有峰值點的總數。

解題策略

1. 將所有格子按高度降序排序。
2. 依序以每個未訪問格子為起點 BFS，記錄可達到的最大高度 v[x][y]。
3. 若 BFS 過程中發現可達高度 > 起點高度，則該起點非峰值。
4. BFS 同時統計同高度連通區域大小（ret），作為峰值點計數貢獻。

關鍵代碼片段

int bfs(int x, int y, int h) {
    int ret = 1; bool flag = true;
    queue<point> que; que.push(point(x, y));
    while (!que.empty()) {
        point u = que.front(); que.pop();
        for (int i = 0; i < 4; i++) {
            int p = u.x + dir[i][0], q = u.y + dir[i][1];
            if (p<=0||p>N||q<=0||q>M) continue;
            if (h - g[p][q] >= D) continue;          // 高度差限制
            if (v[p][q] > h) { flag = false; continue; } // 發現更高點
            if (v[p][q] == h) continue;
            if (g[p][q] == h) ret++;
            v[p][q] = h; que.push(point(p, q));
        }
    }
    return flag ? ret : 0;
}

主循環遍歷排序後的點，跳過已訪問者，累加 BFS 返回值。