题目描述
The farm has many hills upon which Farmer John would like to place guards to ensure the safety of his valuable milk-cows.
He wonders how many guards he will need if he wishes to put one on top of each hill. He has a map supplied as a matrix of integers; the matrix has N (1 < N <= 700) rows and M (1 < M <= 700) columns. Each member of the matrix is an altitude H_ij (0 <= H_ij <= 10,000). Help him determine the number of hilltops on the map.
A hilltop is one or more adjacent matrix elements of the same value surrounded exclusively by either the edge of the map or elements with a lower (smaller) altitude. Two different elements are adjacent if the magnitude of difference in their X coordinates is no greater than 1 and the magnitude of differences in their Y coordinates is also no greater than 1.
农场里有许多山丘，在山丘上约翰要设置哨岗来保卫他的价值连城的奶牛.
约翰不知道有多少山丘，也就不知道要设置多少哨岗.他有一张地图，用整数矩阵的方式描 述了农场N(1 <= N<=700)行M(1 < M<=700)列块土地的海拔高度好 H_ij (0 <= H_ij <= 10,000).请帮他 计算山丘的数量.
一个山丘是指某一个方格，与之相邻的方格的海拔高度均严格小于它.当然，与它相邻的方 格可以是上下左右的那四个，也可以是对角线上相邻的四个.
输入输出格式
输入格式：
-
Line 1: Two space-separated integers: N and M
- Lines 2..N+1: Line i+1 describes row i of the matrix with M
space-separated integers: H_ij
输出格式：
- Line 1: A single integer that specifies the number of hilltops
输入输出样例
8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0
3
说明
There are three peaks: The one with height 4 on the left top, one of the points with height 2 at the bottom part, and one of the points with height 1 on the right top corner.
题目大意：当一个点的相邻的八个点的高度都小于这个点时，这个点是个山丘。求山丘个数。
题解：搜索...这个叫灌水...将点的高度从高到低排序，进行dfs
代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int n,m,cnt,ans,h[702][702],vis[702][702]; struct Node{ int x,y,h; bool operator < (const Node & a) const{return h>a.h;} }node[490009]; void dfs(int x,int y){ vis[x][y]=1; for(int i=-1;i<=1;i++) for(int j=-1;j<=1;j++) if(x+i<0||x+i>n||y+j<0||y+j>m)continue; else if(h[x+i][y+j]<=h[x][y]&&!vis[x+i][y+j])dfs(x+i,y+j); } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ scanf("%d",&node[++cnt].h); h[i][j]=node[cnt].h; node[cnt].x=i;node[cnt].y=j; } sort(node+1,node+cnt+1); for(int i=1;i<=cnt;i++) if(!vis[node[i].x][node[i].y])dfs(node[i].x,node[i].y),ans++; cout<<ans<<endl; return 0; }