Comfortable Cows (USACO Silver 2021 February)

Comfortable Cows (USACO Silver 2021 February)

  1. 因为comfortable的cow有三个邻居，所以只有一边可以再增加，答案是确定的。
  2. 增加cow可能导致新出现comfortable cow，所以还需要再增加。
  3. 坐标需要变大一些，以防出现负的，按最保守估计，把坐标加1000。
  4. i变大的时候，最终出现的牛是i-1时候的超集，所以i-1的时候加上的牛是不需要去掉重加的。 这样可以满足复杂度的要求。
  5. BFS的时候，不变量是：所有周围有3个邻居的cow，都已经被加入到队列中。

ans = total - i

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
int x,y;
 
int grid[3005][3005];
int dr[5]={0, -1, 0, 1, 0}, dc[5]={0, 0, 1, 0, -1};
int total_cows;
queue<pair<int,int>> q;
 
int count(int r, int c){
    if (grid[r][c]==0) return 0;
    int cnt = 0;
    cnt+=grid[r-1][c];
    cnt+=grid[r+1][c];
    cnt+=grid[r][c-1];
    cnt+=grid[r][c+1];
    return cnt;
}
 
void bfs(){
    while(!q.empty()){
        int curr=q.front().first, curc=q.front().second;
        q.pop();
        if (count(curr,curc)!=3) continue;   // number of neighbors changed
        for(int i=1; i<5; i++){              // find empty neighbor position
            int nr=curr+dr[i], nc=curc+dc[i];
            if(grid[nr][nc]==0){             // found position to add cow
                total_cows++;
                grid[nr][nc]=1;
                for (int j=0; j<5; j++){     // add comfortable neighbors and potentially myself to queue
                    int mr=nr+dr[j], mc=nc+dc[j];
                    if (count(mr,mc)==3) 
                        q.push({mr,mc});
                }
            }
        }
    }
}
 
int main(){
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        scanf("%d %d", &x, &y);
        x+=1000;
        y+=1000;
        if (!grid[x][y]) {
            total_cows++;
            grid[x][y]=1;
            for (int i=0; i<5; i++) {   // 0 is myself
                int nr=x+dr[i], nc=y+dc[i];
                if (count(nr,nc)==3) q.push({nr,nc});
            }
            bfs();
        }
        printf("%d\n", total_cows-(i+1));
    }
    return 0;
}