題目描述
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.
?
?
搜索
屠龍寶刀點擊就送
#include <algorithm> #include <cstdio> #include <queue> #define N 705using namespace std; struct node {int h,x,y;bool operator<(node a)const{return h>a.h;} }sf[N*N]; bool vis[N][N]; int n,m,ans,tot,G[N][N],fx[8]={1,-1,0,0,1,1,-1,-1},fy[8]={0,0,-1,1,1,-1,-1,1}; struct Node {int x,y; }; void bfs(int x,int y) {queue<Node>Q;Q.push((Node){x,y});vis[x][y]=1;for(Node now;!Q.empty();){now=Q.front();Q.pop();int H=G[now.x][now.y];for(int i=0;i<8;++i){int tx=now.x+fx[i],ty=now.y+fy[i];if(tx<1||tx>n||ty<1||ty>m||vis[tx][ty]||G[tx][ty]>H) continue;Q.push((Node){tx,ty});vis[tx][ty]=1;}} } int Main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){scanf("%d",&sf[++tot].h);sf[tot].x=i;sf[tot].y=j;G[i][j]=sf[tot].h;}}sort(sf+1,sf+1+tot); for(int i=1;i<=tot;++i){if(vis[sf[i].x][sf[i].y])continue;bfs(sf[i].x,sf[i].y);ans++;}printf("%d\n",ans);return 0; } int sb=Main(); int main(int argc,char *argv[]){;}
?
)
函數)
