题解哈哈哈

字符型不⽅便处理，所以可以使⽤整型数组来⽅便处理
数字 0 表示#
数字 1 表示.
数字2 表示+
G[][]原图
Ans[][]答案图
input()
{
输⼊⾏n,列m
遍历⾏
输⼊这⼀⾏字付串
遍历列
转换为整型数据（0，1，2表示的是什么）
随机标记⼀下从任意⼀个+开始进⾏搜索处理
}
circle(当前x,当前y,上⼀步x,上⼀步y) //判断联通性和环
{
判断当前位置是否已经被访问过
返回0；
联通计数器减少1 //全局
将当前位置标记为已访问。
遍历当前位置的四个相邻位置（上下左右）
每个相邻位置
如果它与上⼀个位置相同或者不是+号（表示可以连接的位置）
则跳过该位置
如果递归调⽤返回0，表示存在环路
直接返回0。
前⾯都处理结束后，代表所有相邻位置都没有环路，
则返回1表示不存在环路。
}
dfs(当前x,当前y,已布线格⼦数量)
{
//单⾏
是否遍历完⼀⾏
更新⾏数和列数
当前⽅案是否已经超过了最优解
结束搜索
访问状态记录清0
//所有⾏
是否便利完所有的⾏
调⽤判断dfs2函数判断是否存在环路
根据结果更新答案地图Ans和最优解res。
结束搜索
//布线
判断是否可以布线
保留当前布线情况
执⾏布线操作
判断是否存在环路circle
继续递归调⽤dfs函数
恢复当前位置状态
//当前不是+
如果当前位置不是+号
继续递归调⽤dfs函数，遍历下⼀个位置。
}
int main()
{
处理输⼊、input函数
dfs搜索（起点x,起点⽤y,已经布线格⼦数量）;
遍历⼆维数组⾏
遍历⼆维数组列
打印图形
}

#include<bits/stdc++.h>
using namespace std;
const int maxn =10+5;
int G[maxn][maxn];//图，0表示墙，1表示.2表示+
int n,m;
char buf[maxn];//输⼊⽤
int vis[maxn][maxn];
int sx,sy;//随机⼀个+号的位置
int res;//答案
int Ans[maxn][maxn];//答案地图
int cnt;//判联通计数器
const int dx[]={-1,0,1,0};
const int dy[]={0,-1,0,1};
void input()//输⼊，顺便给整个地图周围围⼀圈墙，这样就不⽤担⼼越界问题了
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%s",buf);
for(int j=1;j<=m;j++)
{
if(buf[j-1]=='.')
G[i][j]=1;
else if(buf[j-1]=='+')
{
G[i][j]=2;
sx=i;
sy=j;//给随便⼀个+号位置记下来
}
}
}
/*调试代码⽤
for(int i=0;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
cout<<G[i][j];
}
cout<<endl;
}
*/
}
//判断联通性和环
bool dfs2(int x, int y, int prex, int prey){
//x和y表示当前位置的坐标，prex和prey表示上⼀个位置的坐标。
if(vis[x][y])//函数⾸先检查当前位置是否已经被访问过
return 0;
--cnt; //计数器减少1
vis[x][y]=1; //并将当前位置标记为已访问。
for(int k=0;k<4;k++){//遍历当前位置的四个相邻位置（上下左右）
//对于每个相邻位置
//如果它与上⼀个位置相同或者不是+号（表示可以连接的位置），
//则跳过该位置
int tx=x+dx[k];
int ty=y+dy[k];
if((tx==prex&&ty==prey)||G[tx][ty]!=2)
continue;
//否则，递归调⽤dfs2函数，传⼊相邻位置的坐标以及当前位置的坐标。
//如果递归调⽤返回0，表示存在环路，那么直接返回0。
if(!dfs2(tx,ty,x,y))
return 0;//有环
}
return 1;//最后，如果所有相邻位置都没有环路，则返回1表示不存在环路。
}
//⽤于在给定的电路布局中寻找最优布线⽅案。
void dfs(int x, int y, int tot){//x和y表示当前位置的坐标，tot表示已经布线的格⼦数量。
if(y==m+1)//⾸先检查是否遍历完⼀⾏，如果是，则更新⾏数和列数
{
y=1;
x++;
}
//根据当前的布线数量和最优解res进⾏剪枝判断，如果当前⽅案的总布线数量已经超过了最优解，
//那么直接返回，不再继续搜索。
if(0.8*((n-x)*m+m-y+1) + tot <= res)
return;//1
memset(vis,0,sizeof vis);//函数使⽤memset函数将vis数组清零，⽤于记录访问状态
if(x==n+1)//检查是否遍历完所有⾏
{//调⽤dfs2函数判断是否存在环路，并根据结果更新答案地图Ans和最优解res。
cnt=tot;
// bool flag=0;
if(dfs2(sx,sy,-1,-1)&&!cnt)//cnt！=0说明不联通
{
memcpy(Ans,G,sizeof(G));
res=tot;//更新答案
}
return;
}
if(G[x][y]!=0){//函数检查当前位置是否可以布线（即不是墙或者已经被布线）
int t=G[x][y];//保留现场
G[x][y]=2;//如果可以，则将当前位置标记为+号
if(dfs2(x,y,-1,-1))//并递归调⽤dfs2函数判断是否存在环路。如
dfs(x,y+1,tot+1);//只判环，如果存在环路，则继续递归调⽤dfs函数
G[x][y]=t;//记得恢复现场。 恢复当前位置的状态。
}
if(G[x][y]!=2) //如果当前位置不是+号，
dfs(x,y+1,tot);//则继续递归调⽤dfs函数，遍历下⼀个位置。
}
int main()
{
input();
dfs(1,1,0);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(Ans[i][j]==0)
cout << '#';
else if(Ans[i][j]==1)
cout << '.';
else
cout <<'+';
}
cout << " ";
}
}