[文章目录]
Description
FGD小朋友特别喜欢爬山，在爬山的时候他就在研究山峰和山谷。为了能够让他对他的旅程有一个安排，他想知道山峰和山谷的数量。给定一个地图，为FGD想要旅行的区域，地图被分为*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’（山谷）。你的任务是，对于给定的地图，求出山峰和山谷的数量，如果所有格子都有相同的高度，那么整个地图即是山峰，又是山谷。
一开始各种想搜索，然后从高向低搜。发现样例都不过。
后来问CQzhangyu，其实完全不用。我们对于挨着的点，假设大于当前海拔说明当前肯定不是山峰，如果相等，那么bfs，继续搜索。求山谷同理。一遍bfs就可以。（智障害人啊）
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,ans1,ans2,map[1010][1010];
int dx[]={1,1,1,0,0,-1,-1,-1};
int dy[]={1,0,-1,1,-1,1,0,-1};
bool v[1010][1010];
int read()
{
char ch=getchar(); int re=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re;
}
struct node
{
int x,y;
};
queue<node>q;
void bfs(int x,int y)
{
while(!q.empty()) q.pop();
q.push((node){x,y}); int i,xx,yy;
bool fl1=1,fl2=1; v[x][y]=1;
while(!q.empty())
{
x=q.front().x; y=q.front().y; q.pop();
for(i=0;i<8;++i)
{
xx=x+dx[i]; yy=y+dy[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=n)
{
if(map[xx][yy]>map[x][y]) fl1=0;
if(map[xx][yy]<map[x][y]) fl2=0;
if(map[xx][yy]==map[x][y]&&!v[xx][yy]) v[xx][yy]=1,q.push((node){xx,yy});
}
}
}
if(fl1) ans1++;
if(fl2) ans2++;
}
int main()
{
n=read(); int i,j;
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
map[i][j]=read();
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
if(!v[i][j]) bfs(i,j);
printf("%d %d",ans1,ans2);
return 0;
}