「BZOJ1619」[Usaco2008 Nov] Guarding the Farm 保卫牧场
Description
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.
农夫JOHN的农夫上有很多小山丘，他想要在那里布置一些保镖（……）去保卫他的那些相当值钱的奶牛们。 他想知道如果在一座小山丘上布置一名保镖的话，他总共需要招聘多少名保镖。他现在手头有一个用数字矩阵来表示地形的地图。这个矩阵有N行（1 < N < = 100)和M列( 1 < M < = 70) 。矩阵中的每个元素都有一个值H_ij(0 < = H_ij < =10,000)来表示该地区的海拔高度。请你帮助他统计出地图上到底有多少个小山丘。 小山丘的定义是：若地图中一个元素所邻接的所有元素都比这个元素高度要小（或它邻接的是地图的边界），则该元素和其周围所有按照这样顺序排列的元素的集合称为一个小山丘。这里邻接的意义是：若一个元素与另一个横坐标纵坐标和它的横纵坐标相差不超过1，则称这两个元素邻接。 问题名称：guard 输入格式： 第一行：两个由空格隔开的整数N和M 第二行到第N+1行：第I+1行描述了地图上的第I行，有M个由空格隔开的整数：H_ij. 输入样例：(guard.in): 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 输出格式: 第一行：小山丘的个数 输出样例：(guard.out): 3 输出样例解释： 地图上有三个小山丘：每个小山丘的山峰位置分别在左上角（高度为4），右上角（高度为1）和底部（高度为2）。
Input
* 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
Output
* Line 1: A single integer that specifies the number of hilltops
Sample Input
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
Sample Output
HINT
Source
从最高的一个开始灌水
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #define inf 0x7fffffff #define ll long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,cnt,ans; int xx[8]={0,0,1,1,1,-1,-1,-1},yy[8]={1,-1,1,0,-1,1,0,-1}; int mp[705][705]; bool mark[705][705]; struct data{int x,y,t;}a[500005]; bool operator<(data a,data b){return a.t>b.t;} void dfs(int x,int y) { mark[x][y]=1; for(int i=0;i<8;i++) { int nowx=x+xx[i],nowy=y+yy[i]; if(nowx<1||nowy<1||nowx>n||nowy>m)continue; if(mp[nowx][nowy]<=mp[x][y]&&!mark[nowx][nowy])dfs(nowx,nowy); } } int main() { n=read();m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { ++cnt; mp[i][j]=read(); a[cnt].x=i;a[cnt].y=j;a[cnt].t=mp[i][j]; } sort(a+1,a+cnt+1); for(int i=1;i<=cnt;i++) if(!mark[a[i].x][a[i].y]){dfs(a[i].x,a[i].y);ans++;} printf("%d",ans); return 0; } |
OI 课件=>
