UVA12130 Summits(BFS + 贪心)
题目大意：
给你一个h ∗ w 的矩阵，矩阵的每一个元素都有一个值，代表这个位置的高度。题目要求你找出这个图中有多少个位置是峰值点。从每一个点（高度H）出发遍历这个图有一个要求。就是走过的点的高度不能小于等于H - d；成为峰值点的要求就是从这个点出发走到的位置不能有高度大于H的。
解题思路：
由于图非常大。用dfs肯定不行。将这些点依照高度从大到小的排序。然后每一个点作为起点来遍历，假设找到比这个点大的点就说明不是峰值点。而且遍历的过程中就会将途中走过的点标记上它能到的最大高度。假设下次要找的这个点已经被标记过了。就说明这个点能够到达更大的高度。肯定不是峰值点，就不须要遍历。
代码：
#include#include #include using namespace std;const int maxn = 505;int G[maxn][maxn];int vis[maxn][maxn];//标记对于单独的一次遍历中是否有反复遍历的点，标记能否够到达更大的高度int n, m, d;const int dir[4][2] = { { 0, -1}, { 0, 1}, {-1, 0}, { 1, 0}};struct Node { int x, y, v;}node[maxn * maxn], q[maxn * maxn];int cmp (const Node &a, const Node &b) { return a.v > b.v;}int BFS (int k) { int front , rear; int cnt = 1; front = 0; rear = 1; q[front] = node[k]; vis[node[k].x][node[k].y] = node[k].v; bool flag = 1; while (front < rear) { for (int i = 0; i < 4; i++) { int newx = q[front].x + dir[i][0]; int newy = q[front].y + dir[i][1]; if (newx < 0 || newx >= n || newy < 0 || newy >= m) continue; if (G[newx][newy] > node[k].v) { flag = 0;//往下继续遍历 continue; } if (vis[newx][newy] == node[k].v || node[k].v - G[newx][newy] >= d) continue; vis[newx][newy] = node[k].v; if (G[newx][newy] == node[k].v) cnt++; else G[newx][newy] = node[k].v; q[rear].x = newx; q[rear++].y = newy; } front++; } if (flag) return cnt; return 0;}int main () { int T; scanf ("%d", &T); while (T--) { scanf ("%d%d%d", &n, &m, &d); int cnt = 0; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { scanf ("%d", &G[i][j]); node[cnt].x = i; node[cnt].y = j; node[cnt++].v = G[i][j]; } sort (node, node + cnt, cmp); memset (vis, -1, sizeof (vis)); int ans = 0; for (int i = 0; i < cnt; i++) { if (vis[node[i].x][node[i].y] == -1) { ans += BFS(i); } } printf ("%d\n", ans); } return 0;}