UVA 12130 - Summits(BFS+貪心)

UVA 12130 - Summits

題目鏈接

題意：給定一個h * w的圖，每個位置有一個值，現在要求出這個圖上的峰頂有多少個。峰頂是這樣定義的，有一個d值，如果一個位置是峰頂，那麼它不能走到不大於該峰頂高度 - d的位置，如果滿足這個條件下，並且無法走到更高的山峰，那麼它就是峰頂

思路：利用貪心的策略，把所有點丟到優先隊列，每次取出最高的峰值開始找，進行廣搜，搜的過程中記錄下最大值的點的個數，如果這個是峰頂，就加上這個數。判斷是不是峰頂的方法為，如果廣搜過程中，不會找到一個點的能到的最高峰值大於它，那麼它就是峰頂，可以在廣搜過程邊廣搜邊記錄下每個點能到的最大高度，然後這樣一來，其實每個點都只會搜到一次，復雜度為O(h w log(h * w))

代碼：

#include 
#include 
#include 
#include 
using namespace std;

const int N = 505;
const int D[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

int t, h, w, d, g[N][N], vis[N][N];

struct Point {
    int x, y, val;
    Point(int x, int y, int val = 0) {
	this->x = x;
	this->y = y;
	this->val = val;
    }
    bool operator < (const Point& a) const {
	return val < a.val;
    }
};

priority_queue Q;

int bfs(int x, int y, int H) {
    queue Q;
    Q.push(Point(x, y));
    vis[x][y] = H;
    int ans = 1;
    int flag = 1;
    while (!Q.empty()) {
	Point u = Q.front();
	Q.pop();
	for (int i = 0; i < 4; i++) {
	    int xx = u.x + D[i][0];
	    int yy = u.y + D[i][1];
	    if (xx < 0 || xx >= h || yy < 0 || yy >= w) continue;
	    if (H - g[xx][yy] >= d) continue;
	    if (vis[xx][yy] > H) {
		flag = 0;
		continue;
	    }
	    if (vis[xx][yy] == H) continue;
	    if (g[xx][yy] == H) ans++;
	    vis[xx][yy] = H;
	    Q.push(Point(xx, yy));
	}
    }
    if (flag) return ans;
    return 0;
}

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

int main() {
    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]);
		Q.push(Point(i, j, g[i][j]));
	    }
	}
	printf("%d\n", solve());
    }
    return 0;
}