专栏文章

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

AARIS0_0
B3791题解参与者 7已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@mio0er5h
此快照首次捕获于
2025/12/02 11:19
3 个月前
此快照最后确认于
2025/12/02 11:19
3 个月前
查看原文

1. 题意解释

给出一个图，你能够将里面的一些 . 变成 +，要求全部的 + 四连通且无环，求使得 + 数量最多的方案。

2. 思路

暴搜+剪枝。
我们枚举每一个 . 为 + 或 . 的情况进行搜索。
显然这样子会直接 TLE，只有 4040 pts。
因此端上我们的剪枝大法。
剪枝有两种：最优性剪枝和可行性剪枝。
最优性剪枝：若当前固定的 + 的数量与剩余的所有未定的 . 的数量之和比当前最优解还少，直接剪枝。
可行性剪枝：若当前的图中已经有环，则直接剪枝。
判环我们可以再另写一个 DFS，若当前点的下一个点已经被搜过，且下一个点不是这个点的父节点（即上一步的点），则有环。
这里面依然可以剪枝，一旦找到有环就直接返回。
于是我们把上面的两个剪枝套到暴搜里面，就成功地过了。
最后找到答案时还要记得判连通性，依然可以 DFS 解决。

3. 代码实现

AC code:
CPP
#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;
}

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...