J8C. 水星湖 题解

思路

首先看到这个题目，我们可以发现一些性质

• 一棵树如果距离两个或一格处有水，则它就是可以永久存活的，并会向周边扩散出可以永久存活的树。（为了方便，我们将其称之为靠自己永久存活的树）
• 如果一棵树不能靠自己永久存活，则从一棵树蔓延出来的树也不可能使其永久存活，只有人种下去的树可以让他永久存活。（可以使得我们不必考虑蔓延出来的树是什么时候生长出来的）

解题方法

基于上述性质直接模拟。但细节很多，可以参考代码理解，由于笔者水平不够，可能不够完善。

• 首先直接二维数组模拟地图，直接填充水泊。（由于题目保证水泊不重合，则用二维差分复杂度反而更劣）
• 其次种树，先判断以目前条件是否能永久存活。
• 如果上述条件可以满足，则运用 dfs 扫出可以蔓延的地块，和与之联通的尚未死亡的且尚未永久存活的树。并将其标记为可永久存活的树。
• 最后直接统计即可。

Code

#include<bits/stdc++.h> 
using namespace std;
#define int long long

int n,m,q,r,k;
int mp[3050][3050];
int p[3050][3050];

void Men(int a1,int b1,int a2,int b2){
	for(int i=a1;i<=a2;++i){
		for(int j=b1;j<=b2;++j){
			mp[i][j]=1;
		}
	}
}

int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};

int ddx[12]={0,1,0,-1,1,1,-1,-1,0,0,2,-2};
int ddy[12]={1,0,-1,0,-1,1,-1,1,2,-2,0,0};

bool Check(int x,int y,int Time){
	for(int i=0;i<4;++i){
		int nx=x+dx[i],ny=y+dy[i];
		if((nx>0&&ny>0&&nx<=n&&ny<=m)&&(mp[nx][ny]==3&&Time-p[nx][ny]<=k)||mp[nx][ny]==2||mp[nx][ny]==1){
			//与没死的且尚未存活的树相邻
			//与水相邻
			//与可永久存活的树相邻
			//都可以永久存活 
			return 1;
		}
	}
	for(int i=0;i<12;++i){
		int nx=x+ddx[i],ny=y+ddy[i];
		if((nx>0&&ny>0&&nx<=n&&ny<=m)&&mp[nx][ny]==1){
			//满足性质1，可以永久存活 
			return 1;
		}
	}
	return 0;
}

bool Check2(int x,int y){
	for(int i=0;i<4;++i){
		int nx=x+dx[i],ny=y+dy[i];
		if((nx>0&&ny>0&&nx<=n&&ny<=m)&&mp[nx][ny]==1){
			return 1;
		}
	}
	return 0;
}

void dfs(int x,int y,int Time){
	for(int i=0;i<4;++i){
		int nx=x+dx[i],ny=y+dy[i];
		if((nx>0&&ny>0&&nx<=n&&ny<=m)&&mp[nx][ny]==3&&Time-p[nx][ny]<=k){
			//帮助别的树存活 
			mp[nx][ny]=2;
			p[nx][ny]=0;
			dfs(nx,ny,Time);
		}
		if((nx>0&&ny>0&&nx<=n&&ny<=m)&&mp[nx][ny]==0&&Check2(nx,ny)){
			//蔓延 
			mp[nx][ny]=2;
			dfs(nx,ny,Time+1);
			//此处不加一也可以 AC
			//原因见性质 2 
		}
	}
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//关闭流同步，加速读入 
	cin>>n>>m>>q>>r>>k;
	for(int i=1;i<=q;++i){
		int a1,b1,a2,b2;
		cin>>a1>>b1>>a2>>b2;
		Men(a1,b1,a2,b2);
		//直接填充 
	}
	for(int i=1;i<=r;++i){
		int t,x,y;
		cin>>t>>x>>y;
		if(Check(x,y,t)){//以目前的条件能不能永久存活 
			mp[x][y]=2;
			dfs(x,y,t);
			//可以的话就去帮助别的树存活 
			//并且蔓延一下 
		}
		else{
			mp[x][y]=3;
			p[x][y]=t;
			//否则就标记一下 
		}
	}
	//统计 
	int ans=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(mp[i][j]==2){
				++ans;
			}
		}
	}
	cout<<ans<<'\n';
	return 0;
}

时间复杂度

$O(nm)$

空间复杂度

$O(nm)$

结尾

一道好题，完全明白可以极大提升代码能力。
由于笔者太弱，足足调了一天，所以内容不足之处还请大家指出。

标题

思路

解题方法

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code