原题

折半搜索不知道为什么会 WA，求调。

#include<bits/stdc++.h>
#define MAXN 17
using namespace std;
int n,m,mid,cnt1,cnt2,cnt,ans1,ans2,ans;
char mp[MAXN][MAXN];
char ouf1[MAXN][MAXN],ouf2[MAXN][MAXN];
char ouf[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
bool check1(const int &x,const int &y,const int &px,const int &py){
	if(vis[x][y]){
		return false;
	}
	vis[x][y]=true;
	--cnt1;
	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<=mid&&1<=ny&&ny<=m&&mp[nx][ny]=='+'){
			if(!check1(nx,ny,x,y)){
				return false;
			}
		}
	}
	return true;
}
bool check2(const int &x,const int &y,const int &px,const int &py){
	if(vis[x][y]){
		return false;
	}
	vis[x][y]=true;
	--cnt2;
	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(mid<=nx&&nx<=n&&1<=ny&&ny<=m&&mp[nx][ny]=='+'){
			if(!check2(nx,ny,x,y)){
				return false;
			}
		}
	}
	return true;
}
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){
			continue;
		}
		if(nx<mid&&ouf1[nx][ny]!='+'){
			continue;
		}
		if(nx==mid&&mp[nx][ny]!='+'){
			continue;
		}
		if(nx>mid&&ouf2[nx][ny]!='+'){
			continue;
		}
		if(!check(nx,ny,x,y)){
			return false;
		}
	}
	return true;
}
void dfs1(int x,int y,int sum,int mids){
	if(y==m+1){
		++x;
		y=1;
	}
	if(x==mid){
		memset(vis,0,sizeof(vis));
		int sx=-1,sy=-1;
		for(int i=1;i<mid;++i){
			for(int j=1;j<=m;++j){
				if(mp[i][j]=='+'){
					sx=i;
					sy=j;
					break;
				}
			}
			if(sx!=-1&&sy!=-1){
				break;
			}
		}
		if(sx==-1&&sy==-1){
			return;
		}
		cnt1=sum+mids;
		if(check1(sx,sy,-1,-1)&&!cnt1&&ans1<sum){
			for(int i=1;i<mid;++i){
				for(int j=1;j<=m;++j){
					ouf1[i][j]=mp[i][j];
				}
			}
			ans1=sum;
		}
		return;
	}
	if(mp[x][y]=='.'){
		mp[x][y]='+';
		dfs1(x,y+1,sum+1,mids);
		mp[x][y]='.';
	}
	dfs1(x,y+1,sum,mids);
}
void dfs2(int x,int y,int sum,int mids){
	if(y==m+1){
		++x;
		y=1;
	}
	if(x==n+1){
		memset(vis,0,sizeof(vis));
		int sx=-1,sy=-1;
		for(int i=mid+1;i<=n;++i){
			for(int j=1;j<=m;++j){
				if(mp[i][j]=='+'){
					sx=i;
					sy=j;
					break;
				}
			}
			if(sx!=-1&&sy!=-1){
				break;
			}
		}
		if(sx==-1&&sy==-1){
			return;
		}
		cnt2=sum+mids;
		if(check2(sx,sy,-1,-1)&&!cnt2&&ans2<sum){
			for(int i=mid+1;i<=n;++i){
				for(int j=1;j<=m;++j){
					ouf2[i][j]=mp[i][j];
				}
			}
			ans2=sum;
		}
		return;
	}
	if(mp[x][y]=='.'){
		mp[x][y]='+';
		dfs2(x,y+1,sum+1,mids);
		mp[x][y]='.';
	}
	dfs2(x,y+1,sum,mids);
}
void dfs(int dep,int sum,int sum1,int sum2){
//	printf("%d ",dep);
	if(dep==m+1){
		ans1=0;
		dfs1(1,1,sum1,sum);
		ans2=0;
		dfs2(mid+1,1,sum2,sum);
		memset(vis,0,sizeof(vis));
		int sx=-1,sy=-1;
		for(int i=1;i<mid;++i){
			for(int j=1;j<=m;++j){
				if(ouf1[i][j]=='+'){
					sx=i;
					sy=j;
					break;
				}
			}
			if(sx!=-1&&sy!=-1){
				break;
			}
		}
		for(int i=1;i<=m;++i){
			if(mp[mid][i]=='+'){
				sx=mid;
				sy=i;
				break;
			}
		}
		for(int i=mid+1;i<=n;++i){
			for(int j=1;j<=m;++j){
				if(ouf2[i][j]=='+'){
					sx=i;
					sy=j;
					break;
				}
			}
			if(sx!=-1&&sy!=-1){
				break;
			}
		}
		if(sx==-1&&sy==-1){
			return;
		}
		sum+=ans1+ans2;
		cnt=sum;
		if(check(sx,sy,-1,-1)&&!cnt&&sum>ans){
			for(int i=1;i<mid;++i){
				for(int j=1;j<=m;++j){
					ouf[i][j]=ouf1[i][j];
//					putchar(ouf1[i][j]);
				}
//				putchar('\n');
			}
			for(int i=1;i<=m;++i){
				ouf[mid][i]=mp[mid][i];
//				putchar(mp[mid][i]);
			}
//			putchar('\n');
			for(int i=mid+1;i<=n;++i){
				for(int j=1;j<=m;++j){
					ouf[i][j]=ouf2[i][j];
//					putchar(ouf2[i][j]);
				}
//				putchar('\n');
			}
//			putchar('\n');
//			putchar('\n');
			ans=sum;
		}
		return;
	}
	if(mp[mid][dep]=='.'){
		mp[mid][dep]='+';
//		printf("%d\n",dep);
		dfs(dep+1,sum+1,sum1,sum2);
		mp[mid][dep]='.';
	}
	dfs(dep+1,sum,sum1,sum2);
}
int main(){
	register int sum1=0,sum2=0,sum=0;
	scanf("%d %d",&n,&m);
	mid=(n+1)>>1;
	for(register int i=1;i<=n;++i){
		scanf("%s",mp[i]+1);
		for(register int j=1;j<=m;++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]=='+'){
				++sum1;
			}
			ouf1[i][j]=mp[i][j];
		}
	}
	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]=='+'){
				++sum2;
			}
			ouf2[i][j]=mp[i][j];
		}
	}
	dfs(1,sum,sum1,sum2);
//	putchar('\n');
	for(register int i=1;i<=n;++i){
		for(register int j=1;j<=m;++j){
			putchar(ouf[i][j]);
		}
		putchar('\n');
	}
	return 0;
}