题解 P2919 【[USACO08NOV]守护农场Guarding the Farm】

ouuan

2018-07-26 16:02:15

Solution

我其实也想过从高到低搜索这种做法,~~但总感觉自己会写错..~~ 言归正传,我的做法的核心就在于 ### 凡是周围八格有比自己高的,这个格子所在的等高连通块就不可能是一座山丘,反之肯定是 首先我这里说的山丘是严格按照题面意思来的,即比周围都高的等高连通块,而不是从高到低一整个。然后这句话的正确性..~~需要我证吗?自己想想就好了。~~ 所以先扫一遍看看哪些连通块不是答案,然后剩下的数连通块就行了 代码: ``` #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]); } } } ```