当每一只奶牛进来的时候,有可能改变状态的只有与它相邻的四只奶牛(如果存在的话)
所以,每一次新奶牛进来我们只需要判断与它相邻的四头奶牛的状态是否发生改变了就行
#include<iostream>
using namespace std;
const int N = 1010;
bool st[N][N];
bool comfort[N][N];
int n;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int res;
int main(){
cin>>n;
for(int i=0;i<n;i++)
{
int x,y;
scanf("%d %d",&x,&y);
st[x][y]=true;
for(int i=0;i<4;i++)
{
int x1=x+dx[i],y1=y+dy[i];
if(!st[x1][y1]) continue;
if(comfort[x1][y1])
{
res--; //如果邻居奶牛之前是舒适的,周围再加一只,必然变成不舒适
}
else
{
int cnt=0;
for(int i=0;i<4;i++)
{
int x2=x1+dx[i],y2=y1+dy[i];
if(x2>=0&&x2<=1000&y2>=0&&y2<=1000&&st[x2][y2]) cnt++ ;
}
if(cnt==3)
{
res++;
comfort[x1][y1]=true;
}
}
}
cout<<res<<endl;
}
return 0;
}
后来我突然发现,我在这段代码里,没有判断加入第i头奶牛后,第i头奶牛是否舒适,但是也过了
后来我又加上了对第i头牛的判断
#include<iostream>
using namespace std;
const int N = 1010;
bool st[N][N];
bool comfort[N][N];
int n;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int res;
int main(){
cin>>n;
for(int i=0;i<n;i++)
{
int x,y;
scanf("%d %d",&x,&y);
st[x][y]=true;
for(int i=0;i<4;i++)
{
int x1=x+dx[i],y1=y+dy[i];
if(!st[x1][y1]) continue;
if(comfort[x1][y1])
{
res--;
}
else
{
int cnt=0;
for(int i=0;i<4;i++)
{
int x2=x1+dx[i],y2=y1+dy[i];
if(x2>=0&&x2<=1000&y2>=0&&y2<=1000&&st[x2][y2]) cnt++ ;
}
if(cnt==3)
{
res++;
comfort[x1][y1]=true;
}
}
}
int cnt=0;
for(int i=0;i<4;i++)
{
int x1=x+dx[i],y1=y+dy[i];
if(x1>=0&&x1<=1000&y1>=0&&y1<=1000&&st[x1][y1]) cnt++ ;
}
if(cnt==3)
{
res++;
comfort[x][y]=true;
}
cout<<res<<endl;
}
return 0;
}
然后我又重新试了一下改变样例顺序
8
0 1
1 0
1 2
1 1
2 1
2 2
3 1
3 2
第一个代码输出的结果为
而第二个代码输出结果为
是出现分歧的,所以这里大概是y总数据设置的不够完善吧,大概是吧(小心翼翼)