作者：马里奥毛瑞尔小P | 来源：互联网 | 2023-09-15 17:55
2593:USACO2008NovSilver2.GuardingtheFarm题目描述ThefarmhasmanyhillsuponwhichFarmerJoh
2593: USACO 2008 Nov Silver 2.Guarding the Farm
题目描述
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
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
一个山丘是指某一个方格，与之相邻的方格的海拔高度均严格小于它.当然，与它相邻的方 格可以是上下左右的那四个，也可以是对角线上相邻的四个.
输入输出格式
输入格式：
* 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
思路：地图题，不解释，上代码
#include
#include
#include
#include
using namespace std;
struct node
{
int x,y,h;
}a[500000];
int mx[8]={0,0,1,1,1,-1,-1,-1};
int my[8]={-1,1,-1,0,1,-1,0,1};
bool cmp(const node &a,const node &b)
{
return a.h==b.h?a.xb.h;
}
bool vis[701][701];
int cnt;
int n,m;
int map[701][701];
queueq;
void bfs(int now)
{
q.push((node){a[now].x,a[now].y,0});
vis[a[now].x][a[now].y]=1;
while(!q.empty())
{
node u=q.front();
q.pop();
int xx=u.x,yy=u.y,hh=map[xx][yy];
for(int i=0;i<8;i++)
{
int tx=xx+mx[i],ty=yy+my[i];
if(tx<=0||ty<=0||tx>n||ty>m)
continue;
if(hh>=map[tx][ty]&&!vis[tx][ty])
{
vis[tx][ty]=1;
q.push((node){tx,ty,0});
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&map[i][j]);
a[++cnt].x=i,a[cnt].y=j,a[cnt].h=map[i][j];
}
}
int ans=0;
sort(a+1,a+cnt+1,cmp);
for(int i=1;i<=cnt;i++)
{
if(!vis[a[i].x][a[i].y]&&a[i].h!=0)
{
ans++;
//printf("%d %d\n",a[i].x,a[i].y);
bfs(i);
}
}
printf("%d",ans);
}
原文链接
京公网安备 11010802041100号