#2653. 「POI2007」山峰和山谷 Ridges and Valleys

news/2024/2/27 17:45:36

[POI2007]GRZ-Ridges and Valleys

题面翻译

给定一个地图,为小朋友想要旅行的区域,地图被分为n*n的网格,每个格子(i,j) 的高度w(i,j)是给定的。若两个格子有公共顶点,那么他们就是相邻的格子。(所以与(i,j)相邻的格子有(i-1, j-1),(i-1,j),(i-1,j+1),(i,j-1),(i,j+1),(i+1,j-1),(i+1,j),(i+1,j+1))。我们定义一个格子的集合S为山峰(山谷)当且仅当:

1.S的所有格子都有相同的高度。

2.S的所有格子都联通3.对于s属于S,与s相邻的s’不属于S。都有ws > ws’(山峰),或者ws < ws’(山谷)。

你的任务是,对于给定的地图,求出山峰和山谷的数量,如果所有格子都有相同的高度,那么整个地图即是山峰,又是山谷。

输入 第一行包含一个正整数n,表示地图的大小(1<=n<=1000)。接下来一个n*n的矩阵,表示地图上每个格子的高度。(0<=w<=1000000000)

输出 应包含两个数,分别表示山峰和山谷的数量。

感谢@Blizzard 提供的翻译

题目描述

Byteasar loves trekking in the hills. During the hikes he explores all the ridges and valleys in vicinity.

Therefore, in order to plan the journey and know how long it will last, he must know the number of ridgesand valleys in the area he is going to visit. And you are to help Byteasar.

Byteasar has provided you with a map of the area of his very next expedition. The map is in the shape ofa n × n n\times n n×n square. For each field ( i , j ) (i,j) (i,j) belonging to the square(for i , j ∈ { 1 , ⋯ , n } i,j\in \{1,\cdots,n\} i,j{1,,n}), its height w ( i , j ) w_{(i,j)} w(i,j) is given.

We say two fields are adjacent if they have a common side or a common vertex (i.e. the field ( i , j ) (i,j) (i,j) is adjacent to the fields ( i − 1 , j − 1 ) (i-1,j-1) (i1,j1), ( i − 1 , j ) (i-1,j) (i1,j), ( i − 1 , j + 1 ) (i-1,j+1) (i1,j+1), ( i , j − 1 ) (i,j-1) (i,j1), ( i , j + 1 ) (i,j+1) (i,j+1), ( i + 1 , j − 1 ) (i+1,j-1) (i+1,j1), ( i + 1 , j ) (i+1,j) (i+1,j), ( i + 1 , j + 1 ) (i+1,j+1) (i+1,j+1), provided that these fields are on the map).

We say a set of fields S S S forms a ridge (valley) if:

all the fields in S S S have the same height,the set S S S forms a connected part of the map (i.e. from any field in S S S it is possible to reach any other field in S S S while moving only between adjacent fields and without leaving the set S S S),if s ∈ S s\in S sS and the field s ′ ∉ S s'\notin S s/S is adjacent to s s s, then w s > w s ′ w_s>w_{s'} ws>ws(for a ridge) or w s < w s ′ w_s<w_{s'} ws<ws (for a valley).

In particular, if all the fields on the map have the same height, they form both a ridge and a valley.

Your task is to determine the number of ridges and valleys for the landscape described by the map.

TaskWrite a programme that:

reads from the standard input the description of the map, determines the number of ridges and valleys for the landscape described by this map, writes out the outcome to the standard output.

给定一张地势图,求山峰和山谷的数量

输入格式

In the first line of the standard input there is one integer n n n ( 2 ≤ n ≤ 1 000 2\le n\le 1\ 000 2n1 000)denoting the size of the map. Ineach of the following n n n lines there is the description of the successive row of the map. In ( i + 1 ) (i+1) (i+1)'th line(for i ∈ { 1 , ⋯ , n } i\in \{1,\cdots,n\} i{1,,n}) there are n n n integers w ( i , 1 ) , ⋯ , w ( i , n ) w_{(i,1)},\cdots,w_{(i,n)} w(i,1),,w(i,n)( 0 ≤ w i ≤ 1 000 000 000 0\le w_i\le 1\ 000\ 000\ 000 0wi1 000 000 000), separated by single spaces. Thesedenote the heights of the successive fields of the i i i’th row of the map.

输出格式

The first and only line of the standard output should contain two integers separated by a single space -thenumber of ridges followed by the number of valleys for the landscape described by the map.

样例 #1

样例输入 #1

5
8 8 8 7 7
7 7 8 8 7
7 7 7 7 7
7 8 8 7 8
7 8 8 8 8

样例输出 #1

2 1

大致思路

根据题意,我们需要进行两次的判断,一次是山峰,一次是山谷。
本蒟蒻的思路是尝试将整个图push入队,用数组判断是否入队过,每个数进行周围8个位置的判断,山峰如果有大于当前数的,那么这个不是山峰,但我们依然将其入队完成连通块的搜索,打好标记,避免重复,但不计入答案。如果有与当前数相等的,那将其入队,进行下一次的判断。代码实现:

memset(fup,-1,sizeof(fup));
int dx[]={0,-1,0,1,1,1,0,-1,-1};
int dy[]={0,1,1,1,0,-1,-1,-1,0};
int checkup(int xx,int yy){for(int i=1;i<=8;i++){if(xx+dx[i]<=0||xx+dx[i]>n||yy+dy[i]<=0||yy+dy[i]>n)continue;if(fup[xx+dx[i]][yy+dy[i]]==-1){if(m[xx+dx[i]][yy+dy[i]]==m[xx][yy]){fup[xx+dx[i]][yy+dy[i]]=1;q.push(node(xx+dx[i],yy+dy[i]));}}if(m[xx+dx[i]][yy+dy[i]]>m[xx][yy]){return 1;}}return 99;
}
or(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(fup[i][j]==-1){flag=0;fup[i][j]=1;q.push(node(i,j));while(!q.empty()){k=q.front();q.pop();if(k.x<=0||k.x>n||k.y<=0||k.y>n)continue;if(checkup(k.x,k.y)==1)flag=1;}if(flag==0){ansup++;}}}}

记得标记数组清零,队列清零,位置边界!!!!!!!!!!
山谷的判断与山峰的判断基本一致,代码与其说像,不如说基本一致。只不过判断变为了如果周围有小于当前位置数不计入答案,标记数组初值变为最大值。代码实现:

int dx[]={0,-1,0,1,1,1,0,-1,-1};
int dy[]={0,1,1,1,0,-1,-1,-1,0};
memset(fdw,0x7f7f7f7f,sizeof(fdw));
int checkdw(int xx,int yy){for(int i=1;i<=8;i++){if(xx+dx[i]<=0||xx+dx[i]>n||yy+dy[i]<=0||yy+dy[i]>n)continue;if(fdw[xx+dx[i]][yy+dy[i]]==0x7f7f7f7f){if(m[xx+dx[i]][yy+dy[i]]==m[xx][yy]){fdw[xx+dx[i]][yy+dy[i]]=1;q.push(node(xx+dx[i],yy+dy[i]));}}if(m[xx+dx[i]][yy+dy[i]]<m[xx][yy]){return 1;}}return 99;
}
for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(fdw[i][j]==0x7f7f7f7f){flag=0;fdw[i][j]=1;q.push(node(i,j));while(!q.empty()){					k=q.front();q.pop();if(k.x<=0||k.x>n||k.y<=0||k.y>n)continue;if(checkdw(k.x,k.y)==1)flag=1;}if(flag==0){ansdw++;}}}}

其实这个题像是两个题拼起来的

AC CODE

#include<bits/stdc++.h>
using namespace std;
int fup[1222][1222],fdw[1222][1222];
int n,m[1999][1999];
struct node{int x,y;node(int xx=0,int yy=0)/*:x(x),y(y)*/{this->x=xx;this->y=yy;}
}k;
int ansup=0,ansdw=0;
bool flag=0;
queue<node>q;
int dx[]={0,-1,0,1,1,1,0,-1,-1};
int dy[]={0,1,1,1,0,-1,-1,-1,0};
int checkup(int xx,int yy){for(int i=1;i<=8;i++){if(xx+dx[i]<=0||xx+dx[i]>n||yy+dy[i]<=0||yy+dy[i]>n)continue;if(fup[xx+dx[i]][yy+dy[i]]==-1){if(m[xx+dx[i]][yy+dy[i]]==m[xx][yy]){fup[xx+dx[i]][yy+dy[i]]=1;q.push(node(xx+dx[i],yy+dy[i]));}}if(m[xx+dx[i]][yy+dy[i]]>m[xx][yy]){return 1;}}return 99;
}
int checkdw(int xx,int yy){for(int i=1;i<=8;i++){if(xx+dx[i]<=0||xx+dx[i]>n||yy+dy[i]<=0||yy+dy[i]>n)continue;if(fdw[xx+dx[i]][yy+dy[i]]==0x7f7f7f7f){if(m[xx+dx[i]][yy+dy[i]]==m[xx][yy]){fdw[xx+dx[i]][yy+dy[i]]=1;q.push(node(xx+dx[i],yy+dy[i]));}}if(m[xx+dx[i]][yy+dy[i]]<m[xx][yy]){return 1;}}return 99;
}
int main(){cin>>n;memset(fup,-1,sizeof(fup));memset(fdw,0x7f7f7f7f,sizeof(fdw));for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>m[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(fup[i][j]==-1){flag=0;fup[i][j]=1;q.push(node(i,j));while(!q.empty()){k=q.front();q.pop();if(k.x<=0||k.x>n||k.y<=0||k.y>n)continue;if(checkup(k.x,k.y)==1)flag=1;}if(flag==0){ansup++;}}}}while(!q.empty())q.pop();for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(fdw[i][j]==0x7f7f7f7f){flag=0;fdw[i][j]=1;q.push(node(i,j));while(!q.empty()){					k=q.front();q.pop();if(k.x<=0||k.x>n||k.y<=0||k.y>n)continue;if(checkdw(k.x,k.y)==1)flag=1;}if(flag==0){ansdw++;}}}}cout<<ansup<<" "<<ansdw<<endl;return 0;
} 

http://www.ppmy.cn/news/460153.html

相关文章

【Express.js】Sql-ORM 增删改查

Sql-ORM增删改查 ORM框架: 对象关系映射&#xff0c;面对对象sql 本节使用sequelize作为orm-sql框架&#xff0c;数据库为sqlite 准备工作 同样的&#xff0c;需要安装相应的js版数据库Driver&#xff0c;如: PostgreSQL -> pg, mysql/mariadb -> mysql, sqlite ->…

壁纸app上线了 ,欢迎大家下载使用

壁纸精灵,高清壁纸每日更新&#xff0c;壁纸种类多到你想要尖叫&#xff0c;全部免费解锁&#xff0c;满足你对壁纸的一切要求&#xff0c;打造你专属的个性化移动手机壁纸大全 使用中有任何反馈 可私聊处理

按键精灵万能写法轻松驾驭图色脚本

今天分享一套万能写法&#xff0c;利用这套写法可以快速实现想要的功能。需要使用紫猫老师的插件&#xff0c;一般按键都是有自带的。 以找图为例&#xff1a; 找到以数组方式返回&#xff1b;图片序号&#xff1b;图片名&#xff1b;坐标等参数。 Import “zm.luae” Dim re…

如何把视频做成电脑壁纸?Dynamic Wallpaper导入视频壁纸的方法

如何把视频做成电脑壁纸?在日常生活中我们常常会碰到一些好看的视频&#xff0c;想要将其设置为电脑动态壁纸&#xff0c;您可以使用Dynamic Wallpaper这个软件来设置&#xff0c;具体Dynamic Wallpaper导入视频壁纸的方法可以参考如下。 Dynamic Wallpaper导入视频壁纸的方法…

壁纸精灵隐私政策声明

壁纸精灵尊重和保护利用用户的隐私所有的服务。为了向您提供更准确&#xff0c;更人性化的服务&#xff0c;将壁纸精灵使用和披露按照本隐私政策您的个人信息。 但是壁纸精灵将是一个高度的勤勉&#xff0c;审慎义务对待这些信息。除本隐私政策另有规定外&#xff0c;未经您的…

鸿蒙 安卓4.4,换机精灵鸿蒙版下载-换机精灵 鸿蒙版v4.4.9-PC6鸿蒙网

需要调用以下重要权限 - 允许应用程序创建一个使用类型的窗口 TYPE_SYSTEM_ALERT&#xff0c;所有其他应用程序的顶部只有极少数的应用程序应该使用此权限; 这些窗口用于与用户的系统级相互作用, 允许应用程序读取用户联系人数据, 允许应用程序写入用户的联系人数据, 允许应用程…

android 设置壁纸会卡顿,你的安卓手机用久了卡顿吗?只要这样操作保准像新机一样流畅...

原标题&#xff1a;你的安卓手机用久了卡顿吗&#xff1f;只要这样操作保准像新机一样流畅 随着科技的发展&#xff0c;现在手机更新也是非常的给力&#xff0c;当然很多人都在苦恼手机用一段时间久会卡顿&#xff0c;到底是为什么呢&#xff1f;其实是你没有合理的运用手机&am…

小时候的蓝精灵,大家还记得木有哇?

这群可爱的蓝精灵们因为被格格巫追杀而逃出村庄&#xff0c;笨笨误将大家带进了禁地石窟&#xff0c;由于当时是蓝月&#xff0c;所以大伙都被传送到了进入了我们的世界&#xff0c;当今世界的纽约中央公园。在这里他们一方面要赶在格格巫和阿兹猫&#xff08;Azrael&#xff0…

金山的 wifi共享android手机怎莫共享台式机3g无线网络,金山共享精灵:电脑无线管理手机文件的Android应用...

金山共享精灵&#xff1a;电脑无线管理手机文件的Android应用 2011-03-15 17:12:33 来源&#xff1a;TechWeb 扫码可以&#xff1a; 1.在手机上浏览 2.分享给微信好友或朋友圈 摘要&#xff1a; 近日&#xff0c;金山发布了一款Android手机应用&#xff1a;金山共享精灵。它的…

【热门主题:萤火之夜xp桌面】

萤火之夜xp桌面电脑桌面壁纸 系统&#xff1a;WinXP 大小&#xff1a;1.26 MB 主题简介 今天好桌道给大家推荐的这款主题名为萤火之夜xp主题&#xff0c;萤火虫是乡下夏天夜晚的一大特色吧&#xff0c;这款xp主题的壁纸桌面就是一个小女孩拿着瓶子在野外捉萤火虫的情景&#xf…

制作桌面精灵中遇到的一些问题及解决方法

一&#xff0c;qt中在label上显示中文汉字 char *string "中文和English混和string!"; QTextCodec* gbk_codec QTextCodec::codecByName("GBK"); QString gbk_string codec->toUnicode(string); QLabel *label new QLabel(gbk_string) 二&#xff0…

2021爱智先行者—精灵1号的体验分享

文章目录 一、前言二、体验分享1. 精灵1号设备2. EdgerOS3. 开发工具配置4. 我的第一个应用 【本文正在参与"2021爱智先行者-征文大赛"活动】活动地址&#xff1a;https://bbs.csdn.net/topics/602601454 一、前言 最近通过报名爱智先行者的活动&#xff0c;得以有…

目标检测YOLO实战应用案例100讲-基于深度学习的遥感目标检测算法FPGA部署实现研究

基于深度学习的目标检测网络剪枝及FPGA部署 随着科技的发展,人工智能的发展正在促进计算机视觉的智能化广泛应用。如手 机上的语音识别可以将声音转化成文字、门禁识别人脸通行、美颜相机对人像加上跟 踪特效等,这些都是人工智能在我们生活中的应用。 人工智能对图像领域…

简单认识web与http协议

文章目录 web基础域名概述DNS&#xff08;Domain Name System域名系统&#xff09; 域名空间结构 域名实际用法 2. 网页的概念2.1 网页&#xff08;HTTP/HTTPS&#xff09;HTML 概述HTML超文本标记语言 HTML文档的结构头标签中常用标签内容标签中常用标签Web概述具体组成web的主…

【id:20】【1分】D. DS顺序表之循环移位

题目描述 顺序表的移位是循环移位&#xff0c;例如顺序表&#xff1a;1&#xff0c;2&#xff0c;3&#xff0c;4&#xff0c;5&#xff0c;6。如果左移1位&#xff0c;即原来的头元素移动到末尾&#xff0c;其它元素向左移1位&#xff0c;变成2&#xff0c;3&#xff0c;4&…

查询微信被谁投诉方法技巧

1、微信公众号【微信团队】–菜单栏意见反馈–点推送的“此处”–下拉到底其他选项–下拉“其他异常反馈”进入 2、在意见栏输入“我的账号无缘无故被人恶意投诉&#xff0c;严重影响正常工作和沟通。请求严查此人为何投诉我“诸如此类的话语&#xff0c;然后点击提交即可 3、…

探探提醒对方账号异常_探探账号异常不能回复消息怎么办

大家好&#xff0c;我是时间财富网智能客服时间君&#xff0c;上述问题将由我为大家进行解答。 探探账号异常不能回复消息的解决方法是&#xff1a; 1、如果是账号被封&#xff0c;无法回复短信&#xff0c;建议联系客服解封。 2、如果是网络异常导致&#xff0c;建议切换网络再…

Mybatis 查询语句条件为枚举类型时报错处理

通常我们对于数据库中一些枚举字段使用tinyInt类型&#xff0c;而java对象对应的字段很多时候会为了方便定义成short或者int。但这样显然不美观方便&#xff0c;让后面维护的人抠破脑袋找你的常量定义在哪儿&#xff0c;要是没有注释简直让人崩溃。时间久后&#xff0c;没有人知…

【转】oracle查询不到表的问题

ORACLE的问题解决&#xff1a;Ora-00942&#xff1a;表或视图不存在 分类&#xff1a; 数据库 2006-07-05 00:15 10793人阅读 评论(4) 收藏 举报 oracle sql manager 由powerdesigner导入到oracle中时&#xff0c;记得将在oracle中的表名全部用大写。刚开始时&#xff0c;由于表…

oracle查询数据顺序问题

oracle查询数据顺序问题 [问题点数&#xff1a;20分&#xff0c;结帖人gingkoc] 收藏帖子回复 gingkoc 结帖率 50% 在不动表数据的情况下&#xff0c;同一句sql每次查询的数据顺序是否是一致的&#xff1f; 问题点数&#xff1a;20分 0 2016-08-31 11:21:37 回复数 4 只看楼…
最新文章