题目保证所有的草堆构成连通块,我们可以用 dfs 很简单的获得各个草堆的相对位置
如上图所示,白色的方块为草堆的位置,那么他的外周长是绿色的方块个数,其中红色方块个数的贡献是二,也就是说绕着外周长的外面走一圈,看看当前方格挨着几个草堆,这样通过 dfs 就可以将问题解决了。
遍历所有的绿色/红色方块一次且仅以此,搜索到白色那么 ans+1,此方块的任务结束
const int N=2e5+5;
int n,m;
int i,j,k;
//int a[N];
set<pii> all;
map<pii,int> vis;
int ans=0;
bool judge(int x,int y)
{
for(int i=-1;i<=1;i++){
for(int j=-1;j<=1;j++){
if(i==0 && j==0) continue;
if(all.count(mp(x+i,y+j))) return true;
}
}
return false;
}
void dfs(int x,int y)
{
if(all.count(mp(x,y))){ ans++; return ; }
if(vis[mp(x,y)]==1) return ;
else vis[mp(x,y)]=1;
if(judge(x,y)==false) return ;
for(int i=0;i<4;i++) dfs(x+dx[i],y+dy[i]);
}
int main()
{
while(~sd(n)){
int x,y;
int maxx=0,maxy=0;
while(n--){
sdd(x,y);
all.insert(mp(x,y));
if(y>maxy){
maxy=y;
maxx=x;
}
}
dfs(maxx,maxy+1);
pd(ans);
}
return 0;
}