首页 > 代码库 > UVA 12130 - Summits(BFS+贪心)
UVA 12130 - Summits(BFS+贪心)
UVA 12130 - Summits
题目链接
题意:给定一个h * w的图,每个位置有一个值,现在要求出这个图上的峰顶有多少个。峰顶是这样定义的,有一个d值,如果一个位置是峰顶,那么它不能走到不大于该峰顶高度 - d的位置,如果满足这个条件下,并且无法走到更高的山峰,那么它就是峰顶
思路:利用贪心的策略,把所有点丢到优先队列,每次取出最高的峰值开始找,进行广搜,搜的过程中记录下最大值的点的个数,如果这个是峰顶,就加上这个数。判断是不是峰顶的方法为,如果广搜过程中,不会找到一个点的能到的最高峰值大于它,那么它就是峰顶,可以在广搜过程边广搜边记录下每个点能到的最大高度,然后这样一来,其实每个点都只会搜到一次,复杂度为O(hw 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。