题目：P2919 [USACO08NOV]守护农场Guarding the Farm
搜索 - bfs - dfs - 连通块
题目大意：
给出一个
的矩阵，矩阵中的每一格都有一个高度
定义山丘为若干个高度相等且相邻的格子组成的连通块，并满足该连通块的周边的方格的高度都比连通块内方格的高度小
一个方格与他 上、下、左、右、左上、右上、左下、右下 方的格子相邻
我们用BFS遍历连通块，并判断这个连通块是不是山丘。
在往旁边扩展的时候，做一个判断：如果该方格高度与之前的大，就不满足山丘条件，标记
。若遍历到边界或者高度比之前小的方格，不会影响，直接跳过继续遍历即可
注意：如果发现该连通块不为山丘，只是标记一下。无论如何一定要将该连通块遍历完
#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
const int Maxn=710,Maxm=490000+20;
const int dx[]={1,-1,0,0,-1,-1,1,1},dy[]={0,0,-1,1,-1,1,-1,1};
// 注意是往八个方向遍历
struct node{int x,y;node(int u,int v){x=u,y=v;}
};
int a[Maxn][Maxn],vis[Maxn][Maxn];
int n,m,tot,ans;
bool flag[Maxm];
inline int read()
{int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0' && ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();return s*w;
}
inline bool check(int x,int y)
{return (x<1 || y<1 || x>n || y>m);
}
void bfs(int sx,int sy,int k)
{queue <node> q;vis[sx][sy]=k,flag[k]=1;q.push(node(sx,sy));while(q.size()){int x=q.front().x,y=q.front().y;q.pop();for(int i=0;i<8;++i){int u=x+dx[i],v=y+dy[i];if(check(u,v) || a[u][v]<a[x][y])continue;if(a[u][v]>a[x][y]){flag[k]=0;continue;}if(vis[u][v])continue;vis[u][v]=k,q.push(node(u,v));}}
}
int main()
{
// freopen("in.txt","r",stdin);n=read(),m=read();for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)a[i][j]=read();for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)if(!vis[i][j])bfs(i,j,++tot);for(int i=1;i<=tot;++i)if(flag[i])++ans;printf("%d\n",ans);return 0;
}