P7411 [USACO21FEB] Comfortable Cows S 题解

GMOJ
洛谷

大意

有一个矩阵 $T$， Farmer John 每轮会往 $T$ 矩阵中放一个牛，如果这牛旁边恰好有3头牛，则称这个牛是「舒适的」，求每轮 $T$ 矩阵中有多少个牛是「舒适的」。

解法

用一个二维数组 $B$ 记录这个位置旁有多少头牛，每次添加牛时把四周的位置的 $B$ 值加一，然后判断这个位置是否是「舒适的」，如果是，则 $ans$ 加一；如果是4，$ans$ 就减一，如果自己是舒适的，则 $ans$ 加一。

#include <bits/stdc++.h>
#define qint int
using namespace std;
int a[1005][1005],b[1005][1005],fx[5]={0,0,0,1,-1},fy[5]={0,1,-1,0,0};
void read(int& x)
{
    x=0;
    char c=getchar();
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9')
    {
        x=(x*10)+(c-'0');
        c=getchar();
    }
}
int main()
{
	qint n;
	read(n);
	for (int i = 1,x,y,ans=0 ; i <= n ; ++i)
	{
		read(x);
		read(y);
		x++;
		y++;
		b[x][y]=1;
		if (a[x][y]==3)ans++;
		for (int j = 1 ; j <= 4 ; ++j)
		{
			a[x+fx[j]][y+fy[j]]++;
			if (b[x+fx[j]][y+fy[j]]==0) continue;
			if (a[x+fx[j]][y+fy[j]]==3) ans++;
			if (a[x+fx[j]][y+fy[j]]==4) ans--; 
		}
		printf("%d\n",ans);
	}
	return 0;
}

$^{赛时居然还想循环展开卡常，幸好没写}$