题解：P11215 【MX-J8-T3】水星湖

· · 题解

0th 一些约定

我们将湖记为 1，常青树（即题目中“经过充分多时间后” 网格内剩下的树）记为 2，种下的马上死亡的树记为 3，可以长树的地方记为 4。

1st 图的存储

观察数据可得，n,m\le3000，则考虑将整表打出，又因 2s 的时限，可考虑直接在输入时将湖泊进表（实测不超时）。

for(int x=x1;x<=x2;x++){
    for(int y=y1;y<=y2;y++){
         s[x][y]=1;
    }
}

2nd 主要思想

爆搜，以每次种的树为起点，首先检测是否能存活。

s[x+1][y]!=0||s[x-1][y]!=0||s[x][y + 1]!=0||s[x][y-1]!=0

再搜索四方是否有能长出或能常青的树：

int dx[]={0,0,0,1,-1};
int dy[]={0,1,-1,0,0};
for(int i=0;i<=3;i++){
    int nx=dx[i]+x,ny=dy[i]+y;
    if(s[nx][ny]==3||s[nx][ny]==4) dfs(nx, ny);
}

而在我们开始搜的这颗树的位置的四联通内若有：

那么这里将会有一棵常青树。

s[x][y]=2,ans++;

（题目死亡条件：与其相邻的所有位置均为无树存活的陆地，则它会死亡；）\ （题目长树条件：它是一块无树存活的陆地，它与一块湖泊相邻，它在前一秒与一棵存活的树相邻。）

3rd 图的一些其他处理

Ⅰ

种下的，马上死亡的树 ->3

if(!s[x+1][y]!=0||s[x-1][y]!=0||s[x][y + 1]!=0||s[x][y-1]!=0){
//四周都是荒土
   s[t[p].l][t[p].r]=3;//快死了
}

Ⅱ

可以长树的地方 ->4

if(s[x-1][y]==1||s[x+1][y]==1||s[x][y-1]==1||s[x][y+1]==1){
//周围有水
    s[i][j]=4;//可以长
}

4th 一些细节

在遍历种的树的时候，可以使用队列数据结构，每遍历到一个先看是否能立即存活，若不能则 push 进队列里，再在下一次遍历时看下一次有没有可能帮助这棵树存活下来。

node f=q.front();
while(!q.empty()&&f.t<t[p].t){//队列里有快死的树且救不活了（下一个种下的时间比要死的时间完）
    if(s[f.l][f.r]==3) s[f.l][f.r]=0;//成荒土
    q.pop();//重开
    f = q.front();
}
bool flag=check(t[p].l,t[p].r);//能不能存活:s[x+1][y]!=0||s[x-1][y]!=0||s[x][y + 1]!=0||s[x][y-1]!=0
if(flag)dfs(t[p].l,t[p].r);//爆搜
else{
     s[t[p].l][t[p].r]=3;//要死了
     t[p].t+=k;//时间到死的时候
     q.push(t[p]);//进队列
}
p++;

5th 完整代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e3+10,M=1e5+10;
int n,m,qq,r,k,s[N][N],ans;
struct node{
    int l,r,t;
}t[M];
queue<node>q;
inline bool c1(int x,int y){
    return s[x-1][y]==1||s[x+1][y]==1||s[x][y-1]==1||s[x][y+1]==1;
}
inline bool check(int x,int y){
    return s[x+1][y]!=0||s[x-1][y]!=0||s[x][y + 1]!=0||s[x][y-1]!=0;
}
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
void dfs(int x,int y){
    s[x][y]=2,ans++;
    for(int i=0;i<=3;i++){
        int nx=dx[i]+x,ny=dy[i]+y;
        if(s[nx][ny]==3||s[nx][ny]==4) dfs(nx, ny);
    }
}

signed main(){
    cin>>n>>m>>qq>>r>>k;
    for(int i=1;i<=qq;i++){
        int x1,x2,y1,y2;
        cin>>x1>>y1>>x2>>y2;
        for(int x=x1;x<=x2;x++)for(int y=y1;y<=y2;y++) s[x][y] = 1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(s[i][j]==1)continue;
            if(c1(i,j))s[i][j]=4;
        }
    }   
    for(int i=1;i<=r;i++) cin>>t[i].t>>t[i].l>>t[i].r;
    int p=1;
    while(p<=r){
        node f=q.front();
        while(!q.empty()&&f.t<t[p].t){
            if(s[f.l][f.r]==3) s[f.l][f.r]=0;
            q.pop();
            f=q.front();
        }
        bool flag=check(t[p].l,t[p].r);
        if(flag)dfs(t[p].l,t[p].r);
        else{
            s[t[p].l][t[p].r]=3;
            t[p].t+=k;
            q.push(t[p]);
        }
        p++;
    }
    cout<<ans<<'\n';
}