C++(clang++ 11.0.1) 解法, 执行用时: 167ms, 内存消耗: 17656K, 提交时间: 2023-05-24 09:35:13

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e3+7;
const int maxm=1e5+7;
int a[maxm],b[maxm],ans[maxm],n,vis[maxn][maxn],res;
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
struct node
{
	int x,y;
};
void bfs(int x,int y){
	vis[x][y]=2;
	queue<node>Q;
	res--;
	Q.push({x,y});
	while(!Q.empty()){
		node now=Q.front();
		Q.pop();
		for(int i=0;i<4;i++){
			int xx=now.x+dx[i],yy=now.y+dy[i];
			if(xx<0||xx>2000||yy<0||yy>2000||vis[xx][yy]) continue;
			vis[xx][yy]=2;
			res--;
			Q.push({xx,yy});
		}
	}
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
		a[i]+=1000,b[i]+=1000;
		vis[a[i]][b[i]]=1;   //1代表有树,2代表不能走的地方，0代表没有树
	}
	res=2001*2001-n;  //此时空的个数
	bfs(0,0); //改res,最小的清新数量
	for(int i=n;i>=1;i--){
		ans[i]=res++;
		vis[a[i]][b[i]]=0;//砍树过程
        for(int j=0;j<4;j++){
            int xx=a[i]+dx[j],yy=b[i]+dy[j];
            if(vis[xx][yy]==2) {
                bfs(a[i],b[i]);break;}
        }        
	}
	for(int i=1;i<=n;i++)
	printf("%d\n",ans[i]);
	return 0;
}