题解：P7411 [USACO21FEB] Comfortable Cows S

就是一个深搜的过程，每次一头牛加入进来，做以下操作：

1. 判断该位置是否已经有牛。若已经有牛，则说明之前的操作必须使该位置有牛才最优，因此此时可以将答案减去 $1$。

2. 判断该位置是否满足题意。

3. 判断该位置的四个相邻位置是否满足题意。

4. 若有新加牛，则需重复步骤 $2,3$，判断新加牛的位置。

对于判断是否满足题意，只需判断该点周围牛的个数是否为 $3$。

1
2
3
4
5
6
7
8
9
10
11
12

bool check (int x,int y)
{
    if (!vis[{x,y}]) return 0;//若该点没有牛，则不用判断
    int sum = 0;
    for (int i = 0;i < 4;++i)
    {
        int newx = x + dx[i],newy = y + dy[i];
        if (vis[{newx,newy}]) ++sum;
    }
    if (sum == 3) return 1;//刚好为三个
    else return 0;
}

具体重复搜索的过程就是一个裸裸的 $\texttt{dfs}$，写的和其它大佬的差不多，就不展示了。

至于题目中的“注意加入的奶牛的 $x$ 和 $y$ 坐标并不一定需要在范围 $0 \ldots 1000$ 内。”，我是直接使用 STL 中 map，map <pair <int,int>,bool> vis; 来实现对负数的储存的。但是实测速度较慢，要吸氧才能过，因此较好的方法是对输入的坐标均加上一个较大的数，这样能够较好地避免新加的牛的坐标会出现负数的情况。