AcWing 3371. 舒适的奶牛
原题链接
简单
作者:
曦薇
,
2022-05-10 10:20:55
,
所有人可见
,
阅读 181
思路
- 按照题意模拟,当加入一头新奶牛时,更新他自己和他四个相邻位置的奶牛的临近奶牛数量,当数量为 $3$ 时答案 $ans++$ ,当数量为 $4$ 时答案 $ans–$ 。
- 注意下标不能越界。
- 时间复杂度为 $O(n)$ ,空间复杂度为 $O(1000^2)$ 。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
bool st[N][N];
int g[N][N];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
bool check(int x,int y){
if(x<0||y<0) return false;
return true;
}
int main(void){
int num;
scanf("%d",&num);
int ans=0;
while(num--){
int x,y;
scanf("%d%d",&x,&y);
st[x][y]=true;
int x1,y1;
for(int i=0;i<4;i++){
x1=dx[i]+x,y1=dy[i]+y;
if(!check(x1,y1)) continue;
if(st[x1][y1]){
g[x][y]++;
g[x1][y1]++;
}
if(g[x1][y1]==3) ans++;
if(g[x1][y1]==4) ans--;
}
if(g[x][y]==3) ans++;
cout<<ans<<endl;
}
return 0;
}