描述 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）。
输入格式 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
样例输出 SampleOutput
26
来源 Source
Silver
代码 Code
记录每个点高度排降序，每次取未访问过的最高点 bfs 将所有八个方向小于等于它的点设为 False. 中文翻译的数据范围是错的（应该是(1 < N <= 700)(1 < M <= 700)）。
#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;
}