# 【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.

## 输入格式 InputFormat

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.

## 输出格式 OutputFormat

Line 1: A single integer that specifies the number of hilltops

## 样例输入 SampleInput

15 26
45 44 44 43 36 28 27 21 13 20 20 16 8 11 20 14 7 6 1 0 0 0 8 10 11 9
53 59 66 67 60 59 63 73 82 81 76 77 76 75 79 85 88 87 85 93 99 94 103 111 106 102
61 68 78 77 73 75 81 78 71 81 74 83 92 102 102 100 94 100 103 102 102 101 105 104 100 100
62 59 55 59 55 55 60 66 69 69 65 74 70 78 79 71 73 69 69 62 68 75 74 66 71 66
63 56 55 55 55 64 60 67 69 78 71 81 90 98 91 85 84 78 78 87 93 85 82 81 81 79
73 79 87 90 87 80 90 90 96 88 88 87 84 85 84 82 88 94 104 112 107 107 111 110 113 119
80 76 86 94 96 89 89 82 75 75 67 62 65 65 73 77 72 74 78 84 83 84 78 71 71 80
77 87 87 87 84 89 93 93 97 106 104 100 97 92 90 100 95 93 92 99 103 102 109 101 108 106
74 84 91 97 89 98 104 105 115 120 127 130 139 141 140 143 151 156 154 162 167 170 173 182 174 174
80 77 81 74 82 78 72 71 76 73 66 62 66 66 59 52 58 55 50 50 43 49 43 43 43 49
82 86 88 80 85 89 97 89 91 98 93 85 87 91 92 85 85 85 89 89 82 88 88 89 81 91
89 92 91 95 101 97 97 92 97 99 100 109 117 119 111 111 104 98 90 83 81 83 91 87 89 94
90 82 83 89 90 90 87 95 89 92 89 89 89 90 90 95 91 93 92 88 88 98 100 105 109 101
84 94 101 97 90 86 78 88 97 106 101 96 104 108 110 112 116 124 123 123 133 133 132 139 138 134
92 89 98 98 100 103 96 91 97 94 98 106 115 111 103 96 100 98 98 98 104 104 101 96 96 103

26

Silver

BZOJ 1619

## 代码 Code

``````#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
struct point
{
int z,y,x;
}c[500000],f[500000];
const int dx[9]={0,0,0,1,-1,1,1,-1,-1};
const int dy[9]={0,1,-1,0,0,-1,1,-1,1};
int a[701][701];
bool b[701][701];
int i,j,t,n,m,l,r,k,ans;
inline bool comp(point a,point b)
{
return a.z>b.z;
}
void del(int sx,int sy)
{
int i,j,t,k,l,r;
l=0;r=l;f[l].x=sx;f[l].y=sy;
while (r>=l)
{
for (i=1;i<=8;i++)
{
int tx=f[l].x+dx[i];
int ty=f[l].y+dy[i];
if (tx<=0 || ty<=0 || tx>n || ty>m) continue;
if (b[tx][ty]==false) continue;
if (a[tx][ty]>a[f[l].x][f[l].y]) continue;
b[tx][ty]=false;
f[++r].x=tx;f[r].y=ty;
}
l++;
}
}
int main()
{
scanf("%d%d",&n,&m);
t=0;
for (i=1;i<=n;i++) for (j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
c[++t].x=i;c[t].y=j;c[t].z=a[i][j];
}
sort(c+1,c+t+1,comp);
memset(b,true,sizeof(b));
for (i=1;i<=t;i++) if (b[c[i].x][c[i].y])
{
ans++;
del(c[i].x,c[i].y);
}
printf("%d\n",ans);
return 0;
}``````