题解：B3791 [信息与未来 2023] 电路布线

· · 题解

解 1：爆搜+剪枝

暴力搜索很明显是枚举每一个为 . 的点保留原来的状态或者变为 +，最后进行判断。时间复杂度 2^{n\times m}\times n\times m，第一个测试数据就是为了能够通过这样的数据构造的。

考虑剪枝优化。如果当前的答案之后就算加上了理论的全部可以为 + 的地方还是比不过原来的答案，那么就可以直接返回。

这个很像 IDA-star 中的估价函数，只不过这里的最大深度是搜过的答案。

IDA-star 是用于应对最小答案，方法是将答案估小。而这里要求的是最答案，所以应当将答案估大。比如当前答案为 3，最优答案为 5。假如当前答案扩展出来的答案更优，但是估价函数将其估小估到了 4，那就会被击毙从而导致答案可能错误。

这里可以估成之后所有点都为 + 的情况，一定不会 WA。

判断是否形成环也很好弄，并查集、dfs 或者 bfs 都是可以的。这里用了 dfs（带权并查集之前写挂了，现在还在痛恨并查集。），比如走着走着走到了之前标记的点，并且不是上一个点，那就有环。

发现这里的估价函数剪枝可能优化不了时间（原理同 K 短路的 A-star 算法被卡），还需要加上一些剪枝。

比如当前节点加上去就已经是有环的了，那么就不用往后搜。这个限制了指数（虽然本人很蒻算不出最少能卡多少个不对的情况），而且 dfs 判环最多 6\times 6=36，可以当成常数，所以在大数据下不比没剪枝的代码更劣。

加上去就能够 AC 了。

#include<bits/stdc++.h>
#define MAXN 17
using namespace std;
int n,m,sx,sy,cnt,ans;
char mp[MAXN][MAXN];
char ouf[MAXN][MAXN];
char dfn[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
inline int goal(const int &x,const int &y){
    return n*m-(x-1)*m-y;
}
bool check(const int &x,const int &y,const int &px,const int &py){
    if(vis[x][y]){
        return false;
    }
    vis[x][y]=true;
    --cnt;
    for(register int i=0;i<4;++i){
        const int nx=x+dx[i];
        const int ny=y+dy[i];
        if(px==nx&&py==ny){
            continue;
        }
        if(1<=nx&&nx<=n&&1<=ny&&ny<=m&&mp[nx][ny]=='+'){
            if(!check(nx,ny,x,y)){
                return false;
            }
        }
    }
    return true;
}
void dfs(int x,int y,const int &sum){
    if(y==m+1){
        ++x;
        y=1;
    }
    if(sum+goal(x,y)<=ans){
        return;
    }
    if(x==n+1){
        memset(vis,0,sizeof(vis));
        cnt=sum;
        if(check(sx,sy,-1,-1)&&!cnt){
            memcpy(ouf,mp,sizeof(mp));
            ans=sum;
        }
        return;
    }
    if(mp[x][y]=='.'){
        mp[x][y]='+';
        memset(vis,0,sizeof(vis));
        if(check(x,y,-1,-1)){
            dfs(x,y+1,sum+1);
        }
        mp[x][y]='.';
    }
    dfs(x,y+1,sum);
}
int main(){
    register int sum=0;
    scanf("%d %d",&n,&m);
    for(register int i=1;i<=n;++i){
        scanf("%s",mp[i]+1);
        for(register int j=1;j<=m;++j){
            if(mp[i][j]=='+'){
                ++sum;
                sx=i;
                sy=j;
            }
            ouf[i][j]=mp[i][j];
        }
    }
    dfs(1,1,sum);
    for(register int i=1;i<=n;++i){
        for(register int j=1;j<=m;++j){
            putchar(ouf[i][j]);
        }
        putchar('\n');
    }
    return 0;
}

解 2：折半搜索

还是原来的复杂度：2^{n\times m}\times n\times m，折半搜索还是指数级别的优化。

原理是把上半部分搜一遍，把下半部分搜一遍，时间复杂度 2^{\frac{n\times m}{2}}\times 2\times n\times m。

但是具体怎么用折半搜索实现呢？Luogu 上目前没有，我从官方题解上找出了一个方法（本蒻蒻抛弃的自认为难写方法）。

枚举中转点，即在 \frac{n}{2} 的位置，时间复杂度 2^m。之后向两边扩散最大的位置，时间复杂度 2\times 2^{\frac{n}{2}\times m}，最后判断整个有没有环。

但是，本人后面发现折半搜索各种写法的正确性问题：

这里，作者还是希望有人能够评论给出一种正确折半的思路的，谢谢各位观看！

我是错解。