首页 > 代码库 > UVA12130 Summits(BFS + 贪心)
UVA12130 Summits(BFS + 贪心)
UVA12130 Summits(BFS + 贪心)
题目链接
题目大意:
给你一个h ? w 的矩阵,矩阵的每个元素都有一个值,代表这个位置的高度。题目要求你找出这个图中有多少个位置是峰值点。从每个点(高度H)出发遍历这个图有一个要求,就是走过的点的高度不能小于等于H - d;成为峰值点的要求就是从这个点出发走到的位置不能有高度大于H的。
解题思路:
因为图很大,用dfs肯定不行。将这些点按照高度从大到小的排序,然后每个点作为起点来遍历,如果找到比这个点大的点就说明不是峰值点。并且遍历的过程中就会将途中走过的点标记上它能到的最大高度。如果下次要找的这个点已经被标记过了,就说明这个点可以到达更大的高度,肯定不是峰值点,就不需要遍历。
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
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;
}
UVA12130 Summits(BFS + 贪心)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。