题意理解
舒适的定义:当一个有牛的点四周四个点有三个点有牛,那这个牛就是舒适的
每次放一个点进坐标系,统计放入这个牛的点后,舒适的牛有多少
思路
思路很简单,cnt保存舒适的牛的数量,用一个 g 数组来保存每个点的四周有多少头牛,用st数组保存这个点有没有牛,每放一头牛,就将它四周的点的 g 值加一,如果这个点有牛,if它的g值是3,那cnt++,else if它的值是4,cnt–
注意点
这个坐标系的范围有点大,g的数据最多是4,所以类型设置为short,如果设置成int会segmentation fault
CPP代码, 时间复杂度$O(n)$
#include <iostream>
using namespace std;
const int N = 1e5 + 10, M = 1010;
int n, cnt, dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
bool st[M][M];
short g[M][M];
int main()
{
cin >> n;
int x, y, a, b;
while(n --)
{
scanf("%d%d", &x, &y);
st[x][y] = 1;
for(int i = 0; i < 4; i ++)
{
a = x + dx[i], b = y + dy[i];
g[a][b] ++;
if(st[a][b] == 1)
{
if(g[a][b] == 3) cnt ++;
else if(g[a][b] == 4) cnt --;
}
}
printf("%d\n", cnt);
}
return 0;
}