牛客假日团队赛43：B perimeter

先看题目：https://ac.nowcoder.com/acm/contest/5723/B
题目描述：
有一些草堆块放在一些格子里，每个格子只能放一个草堆块，这些草堆块会形成一个连通块，算连通块的外围周长。
解题思路：
我一开始的思路是，每个初始ans是4*N，也就是每个草堆块四个面的周长都算的情况，然后跟据每个草堆块是向外还是向内可以发现每个草堆块朝向连通块内部的边可以去掉。比如，对于某个草堆块能找到一个草堆块与它y相同，但是x比它大，那么就不必加上这个草堆块的朝右的那个边的长度。但实际上一个简单的反例就可以说明这个思想是错误的。

反例：

后来师哥给出了dfs的解法，令我再次感叹自己的弱小。正解来自@The_Flash
怎么想的呢。求最外围的周长，找最外围的点不就完了吗？

也就是说选择一个点，使得从这个点出发，能围住所有绿色的点,然后计算每个红点的贡献，也就是这个红点与几个绿点相连,这个样直接搜就行了。
总而言之，就是去计算每个红点的贡献，同时要保证红点不要一直拓展下去，即不要离绿点太远。起点选取不唯一，只要在外侧就行。
dfs直接搜索就好，如果遇到了草堆，那么把贡献直接加到答案里。为了保证dfs不会跑到离绿点太远的地方，需要加一个check函数，来搜8个方向上是否会有绿点。check函数之所以要看8个方向是因为，比如这个，如果没有粉色点的话，红色是拓展不过去的

代码：

#include<bits/stdc++.h>
using namespace std;
set< pair<int,int> > st;
set< pair<int, int> > vis;
int n;
int ans = 0;
int dx[]={0,0,-1,1,1,1,-1,-1};
int dy[]={1,-1,0,0,1,-1,1,-1};

bool check(int x, int y)
{
    for(int i = 0; i < 8; i++) if(st.count(make_pair(x+dx[i], y+dy[i]))) return 1;
    return 0;
}

void dfs(int x, int y)
{
    if(st.count(make_pair(x, y)) )
    {
        ans++;
        return;
    }
    if(vis.count(make_pair(x, y)) )
    {
        return;
    }
    if(!check(x, y)) return;
    vis.emplace(make_pair(x, y));
    for(int i = 0; i < 4; i++) dfs(x+dx[i], y+dy[i]);
}
int main()
{
    scanf("%d",&n);
    for(int i = 0, x, y ; i < n; i++) scanf("%d %d",&x,&y), st.emplace(make_pair(x, y));
    auto p = *st.begin();
    dfs(p.first-1, p.second);
    printf("%d\n",ans);
}