题解 P2919 【[USACO08NOV]守护农场Guarding the Farm】
ouuan
2018-07-26 16:02:15
我其实也想过从高到低搜索这种做法,~~但总感觉自己会写错..~~
言归正传,我的做法的核心就在于
### 凡是周围八格有比自己高的,这个格子所在的等高连通块就不可能是一座山丘,反之肯定是
首先我这里说的山丘是严格按照题面意思来的,即比周围都高的等高连通块,而不是从高到低一整个。然后这句话的正确性..~~需要我证吗?自己想想就好了。~~
所以先扫一遍看看哪些连通块不是答案,然后剩下的数连通块就行了
代码:
```
#include <iostream>
#include <cstdio>
using namespace std;
void dfs(int x,int y);
int n,m,a[710][710],ans,dir[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}}; //dir数组记录八个方向,之后就只用一个for而不用手写八遍了
bool vis[710][710];
int main()
{
int i,j,k;
cin>>n>>m;
for (i=1;i<=n;++i)
{
for (j=1;j<=m;++j)
{
cin>>a[i][j];
}
}
for (i=1;i<=n;++i)
{
for (j=1;j<=m;++j)
{
for (k=0;k<8;++k)
{
if (a[i][j]<a[i+dir[k][0]][j+dir[k][1]])
{
dfs(i,j); //如果周围八格有比自己高的就把整个连通块的vis设为true
}
}
}
}
for (i=1;i<=n;++i)
{
for (j=1;j<=m;++j)
{
if (!vis[i][j]) //还没有被排除在答案外的连通块就全是答案了
{
++ans;
dfs(i,j);
}
}
}
cout<<ans;
return 0;
}
void dfs(int x,int y)
{
if (vis[x][y]||x==0||y==0||x>n||y>m)
{
return;
}
vis[x][y]=true;
for (int i=0;i<8;++i)
{
if (a[x][y]==a[x+dir[i][0]][y+dir[i][1]])
{
dfs(x+dir[i][0],y+dir[i][1]);
}
}
}
```