题解：P9944 [USACO21FEB] Comfortable Cows B

Laoda_Bryant · 2024-06-29 16:49:03 · 题解

题目传送门 | 更好的体验

思路

由于每次输入 x 和 y 只改变其上下左右的值，所以每次只要更新其相邻的值即可。

• 当某个位置相邻的奶牛数达到 3 时，舒适度加一。
• 当某个位置相邻的奶牛数达到 4 时，舒适度减一。
• 注意：每增加一头奶牛以后，如果该位置相邻正好有三头奶牛，则舒适度也要加一。

  AC code

  #include<bits/stdc++.h>
  #define int long long
  using namespace std;
  int p[1000][1005],x,y;
  int xk[4]={0,1,0,-1},yk[4]={1,0,-1,0};
  bool k[1005][1005];
  int n,a=0;
  signed main(){
    cin>>n;
    while(n--){
        cin>>x>>y;
        k[x][y]=1;
        for(int i=0;i<4;i++){
            if(x+xk[i]<0||y+yk[i]<0||x+xk[i]>1000||y+yk[i]>1000) continue;
            p[x+xk[i]][y+yk[i]]++;
            if(p[x+xk[i]][y+yk[i]]==3&&k[x+xk[i]][y+yk[i]]) a++;
            if(p[x+xk[i]][y+yk[i]]==4&&k[x+xk[i]][y+yk[i]]) a--;
        }
        if(p[x][y]==3) a++;
        cout<<a<<endl;
    }
    return 0;
  }