舒适的奶牛 (应该挺精简的)
感觉挺快的O(n)吧,常数也蛮小的。
思路
每次读入一个奶牛的时候,相邻的四个格子的相邻奶牛数量就会加一。那么出现舒适奶牛的条件需要满足当前格子有奶牛,并且当前格子的相邻奶牛数量等于3.
如果不理解,请看代码注释hh
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int N=100010;
using PII=pair<int,int>;
int n;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int com[1010][1010];//记录每个格子相邻奶牛的数量
bool st[1010][1010];//记录每个格子是否有奶牛
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
int num=0;
while(n--){
int x,y;
cin>>x>>y;
st[x][y]=true;//读入一个奶牛后,标记当前格子有了奶牛
for(int i=0;i<4;i++){//判断当前读入奶牛的四个方向
int a=x+dx[i],b=y+dy[i];
if(a<0||a>1000||b<0||b>1000)continue;//判断越界
if(com[a][b]==3&&st[a][b])num--;
/*如果在添加当前奶牛(x,y)之前,这个(a,b)的格子相邻奶牛数量为3并且有奶牛,
那么因为要添加(x,y)这个奶牛,会影响(a,b)这个奶牛,所以舒适牛数目要减少*/
com[a][b]++;//增加(a,b)奶牛周围区域相邻奶牛数量
if(com[a][b]==3&&st[a][b])num++;
//如果在添加当前奶牛(x,y)之后,这个(a,b)的格子相邻奶牛数量为3并且有奶牛,那么舒适奶牛数目要增加
}
cout<<num<<endl;
}
return 0;
}
牛啊牛啊
我给你踩上去+1