UVA – 12130 Summits

UVA – 12130 Summits

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

Description

Download as PDF

Problem G – Summits

Time limit: 8 seconds

You recently started working for the largest map drawing company in theNetherlands. Part of your job is to determine what the summits in aparticular landscape are. Unfortunately, it is not so easy to determinewhich points are summits and which are not, because we do not want tocall a small hump a summit. For example look at the landscape given bythe sample input.

We call the points of height 3 summits, since there are no higherpoints. But although the points of height 2, which are to theleft of the summit of height 3, are all higher than or equal totheir immediate neighbours, we do notwant to call them summits, because we can reach a higher point fromthem without going to low (the summits of height 3). In contrast,we do want to call the area of height 2 on the right a summit, sinceif we would want to walk to the summit of height 3, we first have todescend to a point with height 0.

After the above example, we introduce the concept of a d-summit. Apoint, with height h, is a d-summit if and only if it isimpossible to reach a higher point without going through an area withheight smaller than or equal to hd.

The problem is, given a rectangular grid of integer heights and aninteger d, to find the number of d-summits.

Input

On the first line one positive number: the number of testcases, atmost 100. After that per testcase:

  • One line with three integers 1 ≤ h ≤ 500, 1 &le w ≤ 500 and 1 ≤ d ≤ 1000000000. h and w are the dimensions of the map. d is as defined in the text.
  • h lines with w integers, where the xth integer on the yth line denotes the height 0 ≤ h ≤ 1000000000 of the point (x, y).

Output

Per testcase:

  • One line with the number of summits.

Sample Input

1
6 10 2
0 0 0 0 0 0 0 0 0 0
0 1 2 1 1 1 1 0 1 0
0 2 1 2 1 3 1 0 0 0
0 1 2 1 3 3 1 1 0 0
0 2 1 2 1 1 1 0 2 0
0 0 0 0 0 0 0 0 0 0

Sample Output

4

The 2007 ACM Northwestern European Programming Contest

题意:多么费解的题目啊,找顶点,假设一个点是最高的话那么就是顶点。假设不是的话,可是它到比它到的点的路径中假设有<=h-d(h为该点的高度)那么就不能去,那么它就是顶点

思路:首先找个性质:假设A->B,C->B,假设HA>HC,由于HA-d>HC-d,那么C->A,所以我们先按高度排序,然后逐个BFS,假设它的周围能找到跟它一样高的点。那么这些点都是顶点。假设遇到已经被较高找到的点。那么它就也能够到那个较高的点。那么它就不是顶点

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN = 510;

struct node {
	int x, y, h;
	node(int _x = 0, int _y = 0, int _h = 0) {
		x = _x;
		y = _y;
		h = _h;
	}
} arr[MAXN*MAXN];
int map[MAXN][MAXN];
int vis[MAXN][MAXN];
int n, m, d;
int cnt;
int dx[4]={1, -1, 0, 0};
int dy[4]={0, 0, 1, -1};
queue<node> q;

int cmp(node a, node b) {
	return a.h > b.h;
}

void cal() {
	memset(vis, -1, sizeof(vis));
	int ans = 0;
	while (!q.empty())
		q.pop();
	for (int i = 0; i < cnt; i++) {
		node cur = arr[i];
		if (vis[cur.x][cur.y] != -1)
			continue;
		int flag = 1;
		int bound = cur.h - d;
		int top = cur.h;
		q.push(cur);
		int tot = 1;
		while (!q.empty()) {
			cur = q.front();
			q.pop();
			vis[cur.x][cur.y] = top;
			for (int i = 0; i < 4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];
				if (nx < 1 || ny < 1 || nx > n || ny > m)
					continue;
				if (map[nx][ny] <= bound)
					continue;
				if (vis[nx][ny] != -1) {
					if (vis[nx][ny] != top)
						flag = 0;
					continue;
				}
				node tmp;
				tmp.x = nx, tmp.y = ny, tmp.h = map[nx][ny];
				vis[nx][ny] = top;
				if (tmp.h == top) 
					tot++;
				q.push(tmp);
			}
		}
		if (flag) 
			ans += tot;
	}
	printf("%d\n", ans);
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d%d", &n, &m, &d);
		cnt = 0;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++) {
				scanf("%d", &map[i][j]);
				arr[cnt++] = node(i, j, map[i][j]);
			}
		sort(arr, arr+cnt, cmp);
		cal();
	}
	return 0;
}

版权声明:本文博客原创文章,博客,未经同意,不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117669.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 微信公众平台、微信公众平台.小程序、微信.开放平台[通俗易懂]

    微信公众平台、微信公众平台.小程序、微信.开放平台[通俗易懂]一个开发者账号如何上线多个小程序?一个小程序账号对应一个小程序,可发布一个小程序上线。如果需要开发多款小程序,请注册新的账号。https://developers.weixin.qq.com/community/develop/doc/000886957d47f87cf9997f47c5b000小程序怎么发布,一套小程序代码怎么同时发布到不同的小程序上面,发布为体验版和正式版本!点击上传旁边的详情按钮,打开配置页面,修改项目addip,吧这个appid修改成需要覆盖的线上小程序id即可https:

  • Eclipse汉化教程详细[通俗易懂]

    Eclipse汉化教程详细[通俗易懂]eclipse汉化包下载建议从:www.vipkes.cn或www.tkres.cn(恬恪学习网)下载,与此教程配套的资料。或从其它渠道下载。 下载完成后,解压压缩包: 打开压缩包后,可看到里面有个“eclipse”的文件夹,再进入该文件夹,可以看到如下两个文件夹:4.复制这两个文件夹,并找到eclipse安装根目录,如果不知道在哪里,请在桌面鼠标右键—》属性—》快捷方式—》打开文件所在位置即可。在eclipse安装目录下,找到以下dropins文件,双…

  • Java网络编程之TCP粘包拆包

    Java网络编程之TCP粘包拆包

  • linux MySQL启动命令

    linux MySQL启动命令linux7:1、servicemysqlstartstopstatus2、/etc/init.d/mysqlstartstop…

  • Java 递归、DFS、回溯

    Java 递归、DFS、回溯DFS/回溯算法如果某问题的解可以由多个步骤得到,而每个步骤都有若干种选择(这些候选方案集可能会依赖之前做出的选择),且可以用递归枚举法实现,则它的工作方式可以用解答树来描述。全排列问题输出数字1~N所能组成的所有全排列publicclassA{/***全排列**@paramargs*/staticVector<Integer>vector=newVector<>();s

  • react父子组件传值

    react父子组件传值react父子组件传值react父子组件传值一、父给子传值1.子组件是函数组件时,通过参数props接收2.子组件是类组件时,通过参数this.props接收二、子给父传值react父子组件传值一、父给子传值1.子组件是函数组件时,通过参数props接收2.子组件是类组件时,通过参数this.props接收二、子给父传值1.由父组件给子组件提供一个回调函数,传递给子组件;2.当子组件给父组件传值时,调用该回调函数3.父组件通过回调函数调用,拿到子组件传来的参数结果:点击按钮后

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号