折半搜索再官方题解上面说的是对于接缝进行折半。即对中间的接缝进行 $2^m$ 的枚举，然后往上和往下扩展出加号最多的方案，为 $2^{\frac{n}{2}\times m}$。

但是拿最后一个样例来说，这样很可能分开的时候不存在回路，合并就有回路了。

比如，分开的结果是：

++++++
+#.+#+

+#+.#+

+#.+#+
++++++

但是合并起来：

++++++
+#.+#+
+#+.#+
+#.+#+
++++++

这样就有最外面的一个环。

然后，我接下来的思路是搜完上面的再在下面搜最大的没环的，但是 Hack 原理和上述类似。

求证正确性或者调代码。

#include<bits/stdc++.h>
#define MAXN 17
using namespace std;
int n,m,sx,sy,mid,cnt,sum,suml,sumr,ansl,ansr,ans;
bool vis[MAXN][MAXN]; 
char mp[MAXN][MAXN],tmp[MAXN][MAXN],ouf[MAXN][MAXN];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
bool check(int x,int y,int px,int py){
//	cout<<"check is running"<<endl;
	if(vis[x][y]){
		return false;
	}
	vis[x][y]=true;
	--cnt;
	for(int i=0;i<4;++i){
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx==px&&ny==py){
			continue;
		}
		if(1<=nx&&nx<=n&&1<=ny&&ny<=m&&mp[nx][ny]=='+'){
			if(!check(nx,ny,x,y)){
				return false;
			}
		}
	}
	return true;
}
void dfsl(int x,int y){
//	cout<<"dfsl is running"<<endl;
	if(y==m+1){
		++x;
		y=1;
	}
	if(x==mid){
		memset(vis,0,sizeof(vis));
		if(check(sx,sy,-1,-1)&&suml+sum>ansl){
			ansl=suml+sum;
			for(int i=1;i<=mid;++i){
				for(int j=1;j<=m;++j){
					tmp[i][j]=mp[i][j];
				}
			}
		}
		return;
	}
	if(mp[x][y]=='.'){
		mp[x][y]='+';
		++suml;
		dfsl(x,y+1);
		--suml;
		mp[x][y]='.';
	}
	dfsl(x,y+1);
}
void dfsr(int x,int y){
//	cout<<"dfsr is running"<<endl;
	if(y==m+1){
		++x;
		y=1;
	}
	if(x==n+1){
		memset(vis,0,sizeof(vis));
		cnt=ansl+sumr;
		if(check(sx,sy,-1,-1)&&!cnt&&ansl+sumr>ansr){
			ansr=ansl+sumr;
			for(int i=mid+1;i<=n;++i){
				for(int j=1;j<=m;++j){
					tmp[i][j]=mp[i][j];
				}
			}
		}
		return;
	}
	if(mp[x][y]=='.'){
		mp[x][y]='+';
		++sumr;
		memset(vis,0,sizeof(vis));
		if(check(sx,sy,-1,-1)){
			dfsr(x,y+1);
		}
		--sumr;
		mp[x][y]='.';
	}
	dfsr(x,y+1);
}
void dfs(int x,int y){
//	cout<<"dfs is running"<<endl;
	if(y==m+1){
		sx=sy=0;
		for(int i=1;i<=m;++i){
			if(mp[mid][i]=='+'){
				sx=mid;
				sy=i;
				break;
			}
		}
		if(!sy){
			return;
		}
		ansl=0;
		dfsl(1,1);
		for(int i=1;i<=mid;++i){
			for(int j=1;j<=m;++j){
				swap(mp[i][j],tmp[i][j]);
			}
		}
		ansr=0;
		dfsr(mid+1,1);
		for(int i=mid+1;i<=n;++i){
			for(int j=1;j<=m;++j){
				swap(mp[i][j],tmp[i][j]);
			}
		}
		cnt=ansr;
//		cout<<ansr<<":"<<endl;
//		for(int i=1;i<=n;++i){
//			for(int j=1;j<=m;++j){
//				cout<<mp[i][j];
//			}
//			cout<<endl;
//		}
		memset(vis,0,sizeof(vis)); 
		if(check(sx,sy,-1,-1)&&!cnt&&ansr>ans){
			ans=ansr;
			for(int i=1;i<=n;++i){
				for(int j=1;j<=m;++j){
					ouf[i][j]=mp[i][j];
				}
			}
		}
//		cout<<"last:"<<cnt<<"  "<<"ans:"<<ans<<endl;
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				mp[i][j]=tmp[i][j];
			}
		}
		return;
	}
	if(mp[x][y]=='.'){
		mp[x][y]='+';
		++sum;
		dfs(x,y+1);
		--sum;
		mp[x][y]='.';
	}
	dfs(x,y+1);
}
int main(){
	scanf("%d %d",&n,&m);
	mid=(n+1)>>1;
	for(int i=1;i<=n;++i){
		scanf("%s",mp[i]+1);
		for(int j=1;j<=m;++j){
			tmp[i][j]=ouf[i][j]=mp[i][j];
		}
	}
	for(int i=1;i<mid;++i){
		for(int j=1;j<=m;++j){
			if(mp[i][j]=='+'){
				++suml;
			}
		}
	}
	for(int i=1;i<=m;++i){
		if(mp[mid][i]=='+'){
			++sum;
		}
	}
	for(int i=mid+1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(mp[i][j]=='+'){
				++sumr;
			}
		}
	}
	dfs(mid,1);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			putchar(ouf[i][j]);
		}
		putchar('\n');
	}
	return 0;
}