描述
http://www.lydsy.com/JudgeOnline/problem.php?id=1619
给出一张图每个点的高度,在一个点上安排守卫可以监视周围所有不高于于当前点的点.也就是类似在一个点上灌水,周围(8格)低于它的点都会有水,然后继续...求最少的守卫数.
分析
首先图中的最高点必须是要灌水的,所以就从当前最高的开始宽搜,有水的点标记掉就好了.
#include <bits/stdc++.h>
#define fst first
#define scd second
using namespace std; typedef pair <int,int> P;
const int maxn=+;
struct node{
int x,y,d;
node(){}
node(int x,int y,int d):x(x),y(y),d(d){}
bool operator < (const node &a) const { return d>a.d; }
}a[maxn*maxn];
int n,m;
int go[][]={-,-,-,,-,,,-,,,,-,,,,};
int Map[maxn][maxn];
bool vis[maxn][maxn];
P q[maxn*maxn]; inline int read(int &x){ x=;int k=;char c;for(c=getchar();c<''||c>'';c=getchar())if(c=='-')k=-;for(;c>=''&&c<='';c=getchar())x=x*+c-'';return x*=k; }
inline void solve(){
int ans=;
for(int i=;i<=n*m;i++){
if(vis[a[i].x][a[i].y]) continue;
ans++;
int l,r;
q[l=r=]=P(a[i].x,a[i].y);
while(l<=r){
P u=q[l++];
for(int j=;j<;j++){
int dx=u.fst+go[j][],dy=u.scd+go[j][];
if(Map[u.fst][u.scd]>=Map[dx][dy]&&!vis[dx][dy]){
vis[dx][dy]=true;
q[++r]=P(dx,dy);
}
}
}
}
printf("%d\n",ans);
}
inline void init(){
read(n); read(m);
for(int i=;i<=n;i++)for(int j=;j<=m;j++) read(Map[i][j]),a[(i-)*m+j]=node(i,j,Map[i][j]);
sort(a+,a++n*m);
for(int i=;i<=m+;i++) Map[][i]=Map[n+][i]=-;
for(int i=;i<=n+;i++) Map[i][]=Map[i][m+]=-;
}
int main(){
init();
solve();
return ;
}
1619: [Usaco2008 Nov]Guarding the Farm 保卫牧场
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 708 Solved: 315
[Submit][Status][Discuss]
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