# BZOJ1619: [Usaco2008 Nov]Guarding the Farm 保卫牧场 （BFS）

Posted by 111qqz on Sunday, April 3, 2016

## 1619: [Usaco2008 Nov]Guarding the Farm 保卫牧场

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 661  Solved: 292
[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.

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

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

3

## HINT

三个山丘分别是：左上角的高度为4的方格，右上角的高度为1的方格，还有最后一行中高度为2的方格．

## Source

Silver

[Submit][Status][Discuss]
HOME Back\

``````/* ***********************************************
Author :111qqz
Created Time :2016年04月03日 星期日 20时01分12秒
File Name :code/bzoj/1619.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int dx8[8]={1,1,1,0,0,-1,-1,-1};
const int dy8[8]={1,0,-1,-1,1,1,0,-1};
const int inf = 0x3f3f3f3f;
const int N=705;
int h[N][N];
int n,m;
bool vis[N][N];
void checkvis();

struct node
{
int x,y;

bool inmaze ()
{
if (x>=1&&y>=1&&x<=n&&y<=m)  return true;
return false;
}

void look()
{
cout<<x<<" "<<y<<endl;
}
}s;
bool ok ( int x,int y)
{
//   if (x-1>=1&&h[x-1][y]>h[x][y])  return false;
//   if (x+1<=n&&h[x+1][y]>h[x][y])  return false;
//   if (y-1>=1&&h[x][y-1]>h[x][y])  return false;
//   if (y+1<=m&&h[x][y+1]>h[x][y])  return false;

for ( int i = 0 ; i < 8 ; i++)
{
int nx = x + dx8[i];
int ny = y + dy8[i];
if (nx<1||nx>n||ny<1||ny>m) continue;
if (h[nx][ny]>h[x][y]) return false;
}
return true;
}

bool bfs( int x,int y)
{
queue<node>q;
s.x = x;
s.y = y;
q.push(s);
vis[x][y] = true;
bool res = true;
while (!q.empty())
{
node pre = q.front() ;q.pop();
//	pre.look();
//	checkvis();

for ( int i = 0 ; i < 8 ; i++)
{
node nxt;
nxt.x = pre.x + dx8[i];
nxt.y = pre.y + dy8[i];
if (!nxt.inmaze()) continue;
if (vis[nxt.x][nxt.y]) continue;
//  vis[nxt.x][nxt.y] = true;
if (h[nxt.x][nxt.y]!=h[pre.x][pre.y]) continue;
{
res = false;
}
if (!ok(nxt.x,nxt.y))
{
res = false;
}
//	    nxt.look();
q.push(nxt);
vis[nxt.x][nxt.y] = true;
}
}

return res;

}

{
for ( int i = 1 ; i <= n ; i++)
{
for ( int j = 1 ; j <= m ; j++)
{
}
cout<<endl;
}
}

void checkvis()
{
for ( int i = 1 ; i <= n ; i++)
{
for ( int j = 1 ; j <= m ; j++)
{
cout<<vis[i][j]<<" ";
}
cout<<endl;
}
}
int main()
{
#ifndef  ONLINE_JUDGE
freopen("code/in.txt","r",stdin);
#endif

ios::sync_with_stdio(false);
cin>>n>>m;
for ( int i = 1 ; i <= n ; i++)
for ( int j = 1 ; j <= m ; j++) cin>>h[i][j];

for ( int i = 1 ; i <= n ; i++)
{
for ( int j = 1 ; j <= m ; j++)
{
}
}
ms(vis,false);
int ans = 0 ;
for ( int i = 1 ; i <= n ; i++)
{
for ( int j = 1 ; j  <= m ; j++)
{
if (vis[i][j]) continue;
if (bfs(i,j))
{
ans++;
//  cout<<i<<" "<<j<<endl;
}
}
}

cout<<ans<<endl;

#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}
``````

``````/* ***********************************************
Author :111qqz
Created Time :2016年04月03日 星期日 21时33分17秒
File Name :code/bzoj/r1619.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <assert.h>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int dx8[8]={1,1,1,0,0,-1,-1,-1};
const int dy8[8]={-1,0,1,1,-1,-1,0,1};
const int inf = 0x3f3f3f3f;
const int N=705;
int n,m;
bool vis[N][N];
int he[N][N];

struct node
{
int x,y;
int val;

bool operator < (node b)const
{
return val>b.val;
}
}h[N*N];

{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void dfs ( int x,int y)
{
vis[x][y] = true;
for ( int i = 0 ; i < 8 ; i++)
{
int nx = x + dx8[i];
int ny = y + dy8[i];

if (nx<1||ny<1||nx>n||ny>m) continue;
if (he[x][y]<he[nx][ny]) continue;
if (vis[nx][ny]) continue;
dfs(nx,ny);
}
}
int main()
{
#ifndef  ONLINE_JUDGE
freopen("code/in.txt","r",stdin);
#endif

cin>>n>>m;
int cnt = 0 ;
for ( int i = 1 ; i <= n ; i++)
for ( int j = 1 ; j <= m ; j++)
{
cin>>he[i][j];
cnt++;
h[cnt].x = i;
h[cnt].y = j;
h[cnt].val = he[i][j];
}

sort(h+1,h+cnt+1);
ms(vis,false);

int ans = 0 ;
for ( int i = 1 ; i <= cnt ; i++)
{
int x = h[i].x;
int y = h[i].y;
assert(x>=1&&x<N);
assert(y>=1&&y<N);
if (!vis[x][y])
{
dfs(x,y);
ans++;
}

}

cout<<ans<<endl;

#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}
``````

「真诚赞赏，手留余香」