电子商务网站界面设计实验报告,知识库管理系统,wordpress 用户量,wordpress 标签绑定二级域名好久没写题解了#xff0c;交一发吧。
题目传送门
思路讲解
我们用一个结构体 struct 存储每一个格子的状态#xff0c;tp 表示格子的类型#xff0c;t 表示如果该格子种过树#xff0c;种树的最近时间#xff0c;die 表示如果该格子有树#xff0c;这棵树会不会永远都…好久没写题解了交一发吧。
题目传送门
思路讲解
我们用一个结构体 struct 存储每一个格子的状态tp 表示格子的类型t 表示如果该格子种过树种树的最近时间die 表示如果该格子有树这棵树会不会永远都不会死亡。
struct block{int tp,t;//0为空地1为湖泊2为种过树bool die;
}g[3003][3003];首先我们要将每个是湖泊的格子的状态设为 1 1 1容易想到用二维差分解决。
然后我们定义一个 bool 类型的二维数组 nl表示该格子是否接近湖泊方便我们决定它长出树后会不会永远不死。
对于每一次种树操作我们进行 bfs 搜索 如果搜到一颗树设这棵树被种下的时间为 x x x如果这棵树在 t i t_i ti 这个时间有没有死亡即 x k ≥ t i xk\ge t_i xk≥ti或者这棵树本身就被标记为不死则说明这相邻的两个树永远都不会死亡。所以将它们标记为永远不死并将该树的位置加入搜索的队列。 如果搜到一块没有树且与湖泊相邻的陆地则在这里长出一颗新的树并将其标记为不死因为它与湖泊相邻。并将搜到它的那棵树也标记为不死因为它与一个不会死亡的树相邻最后将搜到的树加入队列。 否则不进行任何操作。
答案为所有不会死的树的数量。
代码实现
#include bits/stdc.h
using namespace std;
struct block{int tp,t;bool die;
}g[3003][3003];
int di[4][2]{{-1,0},{1,0},{0,-1},{0,1}};
int n,m,q,r,k,cf[3003][3003],sum[3003][3003],ans;
bool nl[3003][3003];
void bfs(int t,int sx,int sy){queueint x,y;x.push(sx),y.push(sy);while(x.size()){int fxx.front(),fyy.front();x.pop(),y.pop();for(int i0;i4;i){int xxfxdi[i][0],yyfydi[i][1];if(xx0 yy0 xxn yym g[xx][yy].tp!1){if(g[xx][yy].tp2){if(g[xx][yy].tkt){if(g[xx][yy].diefalse)g[xx][yy].die1,ans,x.push(xx),y.push(yy);if(g[fx][fy].diefalse)g[fx][fy].die1,ans;}if(g[xx][yy].die)if(g[fx][fy].diefalse)g[fx][fy].die1,ans;}else if(nl[xx][yy]){g[xx][yy]{2,0,1};ans;if(g[fx][fy].diefalse)g[fx][fy].die1,ans;x.push(xx),y.push(yy);}}}}
}
int main(){scanf(%d%d%d%d%d,n,m,q,r,k);for(int i0;iq;i){int a,b,c,d;scanf(%d%d%d%d,a,b,c,d);cf[a][b],cf[a][d1]--,cf[c1][b]--,cf[c1][d1]; //差分}for(int i1;in;i)for(int j1;jm;j){sum[i][j]cf[i][j]sum[i-1][j]sum[i][j-1]-sum[i-1][j-1];//统计前缀和if(sum[i][j])nl[i-1][j]nl[i1][j]nl[i][j-1]nl[i][j1]1;//如果该位置为湖泊则设置和它相邻的所有nl为trueg[i][j]{sum[i][j],0,false};//初始化}for(int i0;ir;i){int t,x,y;scanf(%d%d%d,t,x,y);g[x][y]{2,t,nl[x][y]};ansnl[x][y];//如果该位置与湖泊相邻则将其标记为不死bfs(t,x,y);}printf(%d,ans);return 0;
}完结撒花
