[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\times n$ square. For each field $(i, j)$ belonging to the square(for $i,j\in \{1,\cdots,n\}$ ), its height $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)$ is adjacent to the fields $(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)$ , provided that these fields are on the map).

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

all the fields in $S$ have the same height,the set $S$ forms a connected part of the map (i.e. from any field in $S$ it is possible to reach any other field in $S$ while moving only between adjacent fields and without leaving the set $S$ ),if $s\in S$ and the field $s'\notin S$ is adjacent to $s$ , then $w_s>w_{s'}$ (for a ridge) or $w_s<w_{s'}$ (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$ ( $2\le n\le 1\ 000$ )denoting the size of the map. Ineach of the following $n$ lines there is the description of the successive row of the map. In $(i + 1)$ 'th line(for $i\in \{1,\cdots,n\}$ ) there are $n$ integers $w_{(i,1)},\cdots,w_{(i,n)}$ ( $0\le w_i\le 1\ 000\ 000\ 000$ ), separated by single spaces. Thesedenote the heights of the successive fields of the $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

样例输出 #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;
}