【BZOJ 1102】 [POI2007]山峰和山谷Grz

1102: [POI2007]山峰和山谷GrzTime Limit:10 SecMemory Limit:162 MBSubmit:495Solved:263[Submit][Status][Discuss]Description

FGD小朋友特别喜欢爬山，在爬山的时候他就在研究山峰和山谷。为了能够让他对他的旅程有一个安排，，他想知道山峰和山谷的数量。给定一个地图，为FGD想要旅行的区域，地图被分为n*n的网格，每个格子(i,j) 的高度w(i,j)是给定的。若两个格子有公共顶点，那么他们就是相邻的格子。（所以与(i,j)相邻的格子有(i1, j1),(i1,j),(i1,j+1),(i,j1),(i,j+1),(i+1,j1),(i+1,j),(i+1,j+1)）。我们定义一个格子的集合S为山峰（山谷）当且仅当：1.S的所有格子都有相同的高度。2.S的所有格子都联通3.对于s属于S，与s相邻的s’不属于S。都有ws > ws’（山峰），或者ws < ws’（山谷）。你的任务是，对于给定的地图，求出山峰和山谷的数量，如果所有格子都有相同的高度，那么整个地图即是山峰，又是山谷。

Input

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

Output

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

Sample Input

输入样例158 8 8 7 77 7 8 8 77 7 7 7 77 8 8 7 87 8 8 8 8输入样例255 7 8 3 15 5 7 6 66 6 6 2 85 7 2 5 87 1 0 1 7

Sample Output

输出样例12 1输出样例23 3

HINT

直接暴力找即可。

dfs会爆栈，用bfs。

注意：只要有公共顶点格子就算是连通

#include <iostream>#include <algorithm>#include <cstring>#include <cmath>#include <cstdlib>#include <cstdio>#include <queue>#define mp make_pairusing namespace std;queue<pair<int,int> > q;int cnt,h,l,fx[10][3],v[1005][1005],w[1005][1005],n;bool ok(int x,int y){if (x>0&&x<=n&&y>0&&y<=n)return true;return false;}/*void dfs(int x,int y){v[x][y]=1;for (int i=1;i<=8;i++){int nx=x+fx[i][1],ny=y+fx[i][2];if (!ok(nx,ny)) continue;if (w[nx][ny]==w[x][y]&&!v[nx][ny]){dfs(nx,ny);continue;}if (w[nx][ny]==w[x][y]) continue;cnt++;if (w[nx][ny]>w[x][y]) h++;else l++;}}*/void bfs(int a,int b){q.push(mp(a,b));v[a][b]=1;while (!q.empty()){pair<int,int> p=q.front();q.pop();int x=p.first,y=p.second;for (int i=1;i<=8;i++){int nx=x+fx[i][1],ny=y+fx[i][2];if (!ok(nx,ny)) continue;if (w[nx][ny]==w[x][y]&&!v[nx][ny]){v[nx][ny]=1;q.push(mp(nx,ny));}if (w[nx][ny]!=w[x][y]){cnt++;if (w[nx][ny]>w[x][y]) h++;else l++;}}}}int main(){fx[1][1]=fx[2][1]=0,fx[1][2]=1,fx[2][2]=-1;fx[3][2]=fx[4][2]=0,fx[3][1]=1,fx[4][1]=-1;fx[5][1]=fx[6][1]=1,fx[5][2]=1,fx[6][2]=-1;fx[7][1]=fx[8][1]=-1,fx[7][2]=1,fx[8][2]=-1;scanf("%d",&n);for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)scanf("%d",&w[i][j]);int sf=0,sg=0;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)if (!v[i][j]){cnt=0,h=0,l=0;bfs(i,j);if (h==cnt) sg++;if (l==cnt) sf++;}printf("%d %d\n",sf,sg);return 0;}

每一幢房子都有一种不同的颜色，