UVA 12130 - Summits

题目链接

题意：给定一个h * w的图，每一个位置有一个值。如今要求出这个图上的峰顶有多少个。峰顶是这样定义的。有一个d值，假设一个位置是峰顶。那么它不能走到不大于该峰顶高度 - d的位置。假设满足这个条件下。而且无法走到更高的山峰，那么它就是峰顶

思路：利用贪心的策略。把全部点丢到优先队列，每次取出最高的峰值開始找，进行广搜。搜的过程中记录下最大值的点的个数。假设这个是峰顶。就加上这个数。

推断是不是峰顶的方法为，假设广搜过程中。不会找到一个点的能到的最高峰值大于它，那么它就是峰顶，能够在广搜过程边广搜边记录下每一个点能到的最大高度，然后这样一来，事实上每一个点都仅仅会搜到一次，复杂度为O(h
w log(h * w))

代码：

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <queue>

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<Point> Q;

int bfs(int x, int y, int H) {

    queue<Point> 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;

}