Nowruz题解

题目大意

有一个迷宫和障碍物，“.”是可通行的空格，相邻的两个“.”连成一条边形成一个图，这个（无向）图需要满足以下要求：

• 图中没有环
• 所有的空格是联通的

这也能等价于一棵树，而能藏孩子的地方即是叶子节点，思路显然，这是一道贪心加上搜索的题目，考虑使用 DFS 进行搜索。

思路过程

考虑到数据可能有多个互不连通的联通块，而整个迷宫只能在一个联通块中，那么显而易见使用 BFS 来找出最大联通块，并选取一个格子作为（树的）根，通常可以随机选根运行多次来尝试获得更好的构造。

为了维护树，用 set 集合进行存储未选格子作为候选点并计算可带来的新叶子数，而从 set 中取出元素时要重新计算其余候选点的收益：

• 若收益不变继续维护树
• 收益变化重新插入新值
• 若无法扩展周遭节点则直接丢弃这个值

话说这是不是挺像懒删除。

如果一直进行如上操作，考虑到部分点可能未及时进入 set ，所以每轮扫描结束后再扫描一次全图，找到相邻的未选格子并接入贪心就可以啦。

对于普通扩展可能需要换叶，记录当前树恰好相邻两次的未选节点 $p$ ，若 $p$ 某树的邻居是叶子，可以删除旧叶再加入 $p$ ，即可继续维护树而不形成环，读者注意考虑换叶的收益并产生较好数据的方法是节点 $p$ 能扩展至少四个空格或在 $p$ 两个树邻居皆为叶子时有七个空格可扩展才进行换叶。

因此，本题策略是在最大的空格联通块不断随机选根并运行贪心，利用不同节点形成完全不同的树来选取其中最优的树，收益相同的候选点随机选择，在大样例的过程中不过于专注少数叶子节点来浪费大量时间，优先构造有效高分图。提高效率也可对联通块进行旋转与镜像，进行不同方向搜索，这里不多赘述。

复杂度

• 基础贪心 $O(V \log V)$
• 朴素实现 $O(V^2)$

代码

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

// 内部状态：
// '#'：原有岩石
// '.'：尚未选入迷宫的空格
// 'T'：已经选入当前树的格子
int m,n,k;
vector<string> a;

// 固定为左、上、右、下，方向顺序会影响最终答案
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};

// 元素为：{本次能增加的新叶子数,{行,列}}
set<pair<int,pair<int,int>>> s;

vector<vector<int>> vis;
int tim=0;

// 统计一个格子四周的树格子数量
int around(int x,int y)
{
    int cnt=0;
    for(int d=0;d<4;d++)
        if(a[x+dx[d]][y+dy[d]]=='T') cnt++;
    return cnt;
}

int extend_node(int x,int y,bool act);

// 直接把一个格子加入树，并更新周围候选点
void add_node(int x,int y)
{
    a[x][y]='T';
    for(int d=0;d<4;d++)
    {
        int xx=x+dx[d],yy=y+dy[d];
        if(a[xx][yy]!='.') continue;

        int w=extend_node(xx,yy,0);
        if(w!=-1) s.insert({w,{xx,yy}});
    }
}

// p 只有一个树邻居时，可以安全扩展
// act=0：只计算收益
// act=1：真正执行扩展
int extend_node(int x,int y,bool act)
{
    if(a[x][y]!='.' || around(x,y)!=1) return -1;

    int cnt=0;
    for(int d=0;d<4;d++)
    {
        int xx=x+dx[d],yy=y+dy[d];

        // 这个邻居完全没有接触当前树，加入后会成为新叶子
        if(a[xx][yy]=='.' && around(xx,yy)==0)
        {
            cnt++;
            if(act) add_node(xx,yy);
        }
    }

    if(act) a[x][y]='T';
    return cnt;
}

// 在最大空格连通块中选取按行列顺序最早的格子作为根
void init_tree()
{
    int best=-1,sx=-1,sy=-1;
    vector<vector<int>> used(m+2,vector<int>(n+2,0));

    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if(a[i][j]=='.' && !used[i][j])
            {
                queue<pair<int,int>> q;
                q.push({i,j});
                used[i][j]=1;
                int cnt=0;

                while(!q.empty())
                {
                    int x=q.front().first;
                    int y=q.front().second;
                    q.pop();
                    cnt++;

                    for(int d=0;d<4;d++)
                    {
                        int xx=x+dx[d],yy=y+dy[d];
                        if(a[xx][yy]=='.' && !used[xx][yy])
                        {
                            used[xx][yy]=1;
                            q.push({xx,yy});
                        }
                    }
                }

                if(cnt>best)
                {
                    best=cnt;
                    sx=i;
                    sy=j;
                }
            }

    if(sx!=-1) add_node(sx,sy);
}

// 估计从入口 (sx,sy) 后面还能利用多少个空格
int free_area_size(int sx,int sy)
{
    tim++;
    vector<pair<int,int>> st;
    st.push_back({sx,sy});
    vis[sx][sy]=tim;
    int cnt=0;

    while(!st.empty())
    {
        int x=st.back().first;
        int y=st.back().second;
        st.pop_back();
        cnt++;

        for(int d=0;d<4;d++)
        {
            int xx=x+dx[d],yy=y+dy[d];
            if(a[xx][yy]=='.' && vis[xx][yy]!=tim
                && around(xx,yy)==0)
            {
                vis[xx][yy]=tim;
                st.push_back({xx,yy});
            }
        }
    }

    return cnt;
}

void solve()
{
    init_tree();

    while(1)
    {
        // 第一阶段：不断执行当前收益最大的安全扩展
        while(!s.empty())
        {
            auto t=*s.rbegin();
            s.erase(prev(s.end()));

            int x=t.second.first;
            int y=t.second.second;
            int now=extend_node(x,y,0);

            // 候选信息可能已经过时，取出后重新计算
            if(now==t.first) extend_node(x,y,1);
            else if(now!=-1) s.insert({now,{x,y}});
        }

        bool changed=0;

        // 局部修改后可能产生新的普通候选点
        for(int i=1;i<=m && !changed;i++)
            for(int j=1;j<=n && !changed;j++)
                if(a[i][j]=='.' && around(i,j)==1)
                {
                    add_node(i,j);
                    changed=1;
                }

        if(changed) continue;

        // 第一类换叶：后面立刻能长出至少两个新分支
        for(int i=1;i<=m && !changed;i++)
            for(int j=1;j<=n && !changed;j++)
                if(a[i][j]=='.' && around(i,j)==2)
                {
                    int cnt=0;
                    for(int d=0;d<4;d++)
                    {
                        int x=i+dx[d],y=j+dy[d];
                        if(a[x][y]=='.' && around(x,y)==0) cnt++;
                    }

                    if(cnt<2) continue;

                    for(int d=0;d<4;d++)
                    {
                        int x=i+dx[d],y=j+dy[d];

                        // 删除一个相邻旧叶子，再把入口接入
                        if(a[x][y]=='T' && around(x,y)==1)
                        {
                            a[x][y]='.';
                            add_node(i,j);
                            changed=1;
                            break;
                        }
                    }
                }

        if(changed) continue;

        // 第二类换叶：立即收益不明显，但入口后方区域足够大
        for(int i=1;i<=m && !changed;i++)
            for(int j=1;j<=n && !changed;j++)
                if(a[i][j]=='.' && around(i,j)==2)
                {
                    int siz=free_area_size(i,j);
                    int leaf_cnt=0;

                    for(int d=0;d<4;d++)
                    {
                        int x=i+dx[d],y=j+dy[d];
                        if(a[x][y]=='T' && around(x,y)==1)
                            leaf_cnt++;
                    }

                    if(siz<4) continue;
                    if(leaf_cnt==2 && siz<7) continue;

                    for(int d=0;d<4;d++)
                    {
                        int x=i+dx[d],y=j+dy[d];
                        if(a[x][y]=='T' && around(x,y)==1)
                        {
                            a[x][y]='.';
                            add_node(i,j);
                            changed=1;
                            break;
                        }
                    }
                }

        if(!changed) break;
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>m>>n>>k;

    // 加一圈岩石边界，避免每次判断是否越界
    a.assign(m+2,string(n+2,'#'));
    vis.assign(m+2,vector<int>(n+2,0));

    for(int i=1;i<=m;i++)
    {
        string str;
        cin>>str;
        for(int j=1;j<=n;j++)
            a[i][j]=str[j-1];
    }

    solve();

    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]=='T') cout<<'.';
            else if(a[i][j]=='.') cout<<'X';
            else cout<<'#';
        }
        cout<<'\n';
    }

    return 0;
}

Tips

提交答案注意十个答案直接压缩不要再带一个文件夹要不然会交不了，如果代码等了一分钟还没出结果不一定是你的代码有问题，而且极大概率是这个题目的代码确实要跑很长一段时间（雾），合理使用 checker 去检验自己的答案哦。

:::info[AI使用说明] 本题解写作完成后使用 DeepSeek 进行润色和提高代码可读性 :::