B3791 [信息与未来 2023] 电路布线 题解
1. 题意解释
给出一个图，你能够将里面的一些 . 变成 +，要求全部的 + 四连通且无环，求使得 + 数量最多的方案。
2. 思路
暴搜+剪枝。
我们枚举每一个 . 为 + 或 . 的情况进行搜索。
显然这样子会直接 TLE，只有
因此端上我们的剪枝大法。
剪枝有两种：最优性剪枝和可行性剪枝。
最优性剪枝：若当前固定的 + 的数量与剩余的所有未定的 . 的数量之和比当前最优解还少，直接剪枝。
可行性剪枝：若当前的图中已经有环，则直接剪枝。
判环我们可以再另写一个 DFS，若当前点的下一个点已经被搜过，且下一个点不是这个点的父节点（即上一步的点），则有环。
这里面依然可以剪枝，一旦找到有环就直接返回。
于是我们把上面的两个剪枝套到暴搜里面，就成功地过了。
最后找到答案时还要记得判连通性，依然可以 DFS 解决。
3. 代码实现
AC code:
#include<bits/stdc++.h>
using namespace std;
int n,m,maxn=-1e9,vis[10][10],flag;
char mp[10][10],ans[10][10];
void Dfs(int x,int y,int lx,int ly){//DFS 判环和判连通性
vis[x][y]=1;
if(vis[x][y-1]&&(x!=lx||y-1!=ly)&&y-1>0){
flag=1;
return ;
}
if(vis[x][y+1]&&(x!=lx||y+1!=ly)&&y+1<=m){
flag=1;
return ;
}
if(vis[x-1][y]&&(x-1!=lx||y!=ly)&&x-1>0){
flag=1;
return ;
}
if(vis[x+1][y]&&(x+1!=lx||y!=ly)&&x+1<=n){
flag=1;
return ;
}//这个点的下一个点是其父节点，则有环
if(mp[x+1][y]=='+'&&!vis[x+1][y]&&x+1<=n){
Dfs(x+1,y,x,y);
}
if(mp[x-1][y]=='+'&&!vis[x-1][y]&&x-1>0){
Dfs(x-1,y,x,y);
}
if(mp[x][y+1]=='+'&&!vis[x][y+1]&&y+1<=m){
Dfs(x,y+1,x,y);
}
if(mp[x][y-1]=='+'&&!vis[x][y-1]&&y-1>0){
Dfs(x,y-1,x,y);
}
return ;
}
bool checkcircle(){//判环函数主体
int p=0,q=0;
flag=0;
memset(vis,0,sizeof vis);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mp[i][j]=='+'){
p=i,q=j;//找到第一个 + 的位置
break;
}
}
}
if(p==0&&q==0){//没找到 + 就直接返回
return true;
}
Dfs(p,q,0,0);
if(flag){
return false;
}
return true;
}
bool checkconnect(){//判连通性函数主体
int p=0,q=0;
flag=0;
memset(vis,0,sizeof vis);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mp[i][j]=='+'){
p=i,q=j;//找到第一个 + 的位置
break;
}
}
}
if(p==0&&q==0){//没找到 + 就直接返回
return true;
}
Dfs(p,q,0,0);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mp[i][j]=='+'&&!vis[i][j]){//如果有 + 没被 DFS 到说明不连通
return false;
}
}
}
return true;
}
bool checkmax(int x,int y,int cnt){//最优性剪枝
for(int i=y+1;i<=m;i++){
if(mp[x][i]=='.'){
cnt++;
}
}
for(int i=x+1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mp[i][j]=='.'){
cnt++;
}
}
}//找到还没搜索过的所有 . 并累计数量
if(cnt>maxn){
return true;
}
return false;
}
void dfs(int x,int y,int cnt){//搜索主体
if(x==n+1){//搜到第 n+1 行说明搜完了
if(maxn<cnt){
if(checkcircle()){
if(checkconnect()){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ans[i][j]=mp[i][j];//存答案
}
}
maxn=cnt;//更新最优解
}
}
}
return ;
}
if(mp[x][y]!='.'){
if(mp[x][y]=='+'){
if(checkcircle()){
if(checkmax(x,y,cnt+1)){//双剪枝
if(y==m){
dfs(x+1,1,cnt+1);
}
else{
dfs(x,y+1,cnt+1);
}
}
}
}
else{
if(checkcircle()){
if(checkmax(x,y,cnt)){//双剪枝
if(y==m){
dfs(x+1,1,cnt);
}
else{
dfs(x,y+1,cnt);
}
}
}
}
}
else{
mp[x][y]='+';
if(checkmax(x,y,cnt+1)){
if(checkcircle()){//双剪枝
if(y==m){
dfs(x+1,1,cnt+1);
}
else{
dfs(x,y+1,cnt+1);
}
}
}
mp[x][y]='.';
if(checkmax(x,y,cnt)){
if(checkcircle()){//双剪枝
if(y==m){
dfs(x+1,1,cnt);
}
else{
dfs(x,y+1,cnt);
}
}
}
}
return ;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
}
}
dfs(1,1,0);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<ans[i][j];
}
cout<<'\n';
}
return 0;
}