题目链接:uva 12130 - Summits
题目大意:给定一个N∗M的图,每个位置有一个值。给定D,表示有节点值为G的位置作为起点的话,将不能移动到值小于等于G−D的节点。现在要求找到整个图中所有的峰值点,峰值点的定义是不能移动到比自己节点值大的位置。
解题思路:将每个位置按照权值排序,逐个作为起点进行移动,v[x][y]数组值可以到达x,y的节点的值的最大值,如果起始点可以移动到v[x][y]大于本身的点,则说明该起点不是峰值点。
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 505;
const int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
struct point {
int x, y, val;
point (int x = 0, int y = 0, int val = 0) {
this->x = x;
this->y = y;
this->val = val;
}
bool operator < (const point& u) const {
return val > u.val;
}
};
int N, M, D, g[maxn][maxn], v[maxn][maxn];
vector<point> vec;
void init () {
vec.clear();
memset(v, 0, sizeof(v));
scanf("%d%d%d", &N, &M, &D);
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
scanf("%d", &g[i][j]);
vec.push_back(point(i, j, g[i][j]));
}
}
sort(vec.begin(), vec.end());
}
int bfs (int x, int y, int h) {
int ret = 1;
bool flag = true;
queue<point> que;
que.push(point(x, y));
while (!que.empty()) {
point u = que.front();
que.pop();
for (int i = 0; i < 4; i++) {
int p = u.x + dir[i][0];
int q = u.y + dir[i][1];
if (p <= 0 || p > N || q <= 0 || q > M)
continue;
if (h - g[p][q] >= D)
continue;
if (v[p][q] > h) {
flag = false;
continue;
}
if (v[p][q] == h)
continue;
if (g[p][q] == h)
ret++;
v[p][q] = h;
que.push(point(p, q));
}
}
if (flag == false)
return 0;
return ret;
}
int solve () {
int ret = 0;
for (int i = 0; i < vec.size(); i++) {
int x = vec[i].x, y = vec[i].y;
if (v[x][y])
continue;
v[x][y] = g[x][y];
ret += bfs(x, y, g[x][y]);
}
return ret;
}
int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
init();
printf("%d\n", solve());
}
return 0;
}
分享到:
相关推荐
The Android Developer's Cookbook (7Summits).pdf The Android Developer's Cookbook (7Summits).pdf
Android Application Development for Dummies (7Summits) 一本不错的安卓开发教程,英文
Sams Teach Yourself Android Application Development in 24 Hours (7Summits) 适合新手
一本专业顶级的安卓开发书,不过要有一定的基础才行
如果你是一个刚开始学习安卓的开发者,这个是很好用的一本书
Generative AI breakthroughs, major developments in the field of AI regulation like the European Union’s AI Act, and a significant increase in AI-related summits globally have put this technology in ...
开发者峰会演讲在这里,您可以访问过去几年的开发者峰会中使用的演示和演示。2021年2020年2019年2018年2017年
people were coming to summits to figure out what OpenStack was.
2011年OLS大会的论文集。The Linux Symposium (commonly referred to as OLS, from ... It features 100+ paper presentations, tutorials, birds of a feather sessions and mini summits on a wide range of topics.
2010年OLS大会的论文集。The Linux Symposium (commonly referred to as OLS, from ... It features 100+ paper presentations, tutorials, birds of a feather sessions and mini summits on a wide range of topics.