DFS 2025/1/15

DFS & DFS 剪枝优化

Basic
01	先搜节点少的分支
如果搜进来一个大分支而答案不在此分支就会浪费大量时间 

02  可行性剪枝
已经白扯了就 return

03  最优性剪枝
如果此分支确定不是最优解(差于已有解)就 return

04  记忆化搜索
记录之前搜过 Data ,避免重复搜


Question 01 [ACP1682 红与黑]
模板题,注意长宽输入顺序与常见顺序相反

Code
#include<bits/stdc++.h>
using namespace std;
const int N=35;
int n,m,sx,sy,dx[6]={0,1,0,0,-1},dy[6]={0,0,1,-1,0},ans;
char mp[N][N];
void dfs(int x,int y){
	++ans;
	mp[x][y]='#';
	for(int i=1;i<=4;i++){
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(xx<1||yy<1||xx>n||yy>m)continue;
		if(mp[xx][yy]=='#')continue;
		dfs(xx,yy);
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	while(true){
		ans=0;
		cin>>m>>n;
		if(n==0&&m==0)return 0;
		for(int i=1;i<=n;i++){
			cin>>mp[i]+1;
			for(int j=1;j<=m;j++)if(mp[i][j]=='@')sx=i,sy=j,mp[i][j]='.';
		}
		dfs(sx,sy);
		cout<<ans<<"\n";
	}
} 


Question 02 [ACP1685 马走日]
[dfs +回溯]模板
注意使用下述写法需要特殊标记起点
因为使用了回溯
所以不需要 memset 了
 
Code
#include<bits/stdc++.h>
using namespace std;
const int N=10;
int n,m,x,y,st[N][N],ans;
const int dx[10]={0,1,1,2,2,-1,-1,-2,-2},dy[10]={0,-2,2,-1,1,-2,2,-1,1};
void dfs(int x,int y,int step){
	if(step==n*m){
		++ans;
		return;
	}
	for(int i=1;i<=8;i++){
		int xx=x+dx[i],yy=y+dy[i];
		if(xx<0||yy<0||xx>=n||yy>=m)continue;
		if(st[xx][yy])continue;
		st[xx][yy]=true;
		dfs(xx,yy,step+1);
		st[xx][yy]=false;
	}
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		ans=0;
		scanf("%d%d%d%d",&n,&m,&x,&y);
		st[x][y]=1;
		dfs(x,y,1);
		st[x][y]=0;
		printf("%d\n",ans);
	}
	return 0;
} 

Question 03 [ACP2512 小猫爬山]
这题 luogu 只有橙
但卡了我 1e9+7 秒
显然是我太菜了

Answer
记录当前每一个车的已有载重
用每一只猫去选择坐哪一辆车
dfs 的两维分别是猫的下标和已有的花费 
首先先枚举"蹭"上哪一辆车
最终再统计一下单开一辆车的最优答案  
本题使用了优化技巧
Basic 01 和 Basic 03
经作者测试如果不是先从大到小进行排序 
很难在一秒内通过
dfs 的部分还加入了最优性剪枝 
记录局部最优答案与当前答案进行对比 
如果发现当前答案已超过局部最优答案就直接舍弃掉该分支

Code
#include<bits/stdc++.h>
using namespace std;
const int N=20;
int cat[N],n,lim,car[N],ans=1000;
void dfs(int cat_id,int money){
	if(money>ans)return;
	if(cat_id>n){ans=min(ans,money);return;}
	for(int i=1;i<=money;i++){
		if(cat[cat_id]+car[i]<=lim){
			car[i]+=cat[cat_id];
			dfs(cat_id+1,money);
			car[i]-=cat[cat_id];
		}
	}
	car[money+1]=cat[cat_id];
	dfs(cat_id+1,money+1);
	car[money+1]=0;
}
bool cmp(int a,int b){return a>b;} 
int main(){
	scanf("%d%d",&n,&lim);
	for(int i=1;i<=n;i++)scanf("%d",&cat[i]);
	sort(cat+1,cat+n+1,cmp);
	dfs(1,0);
	printf("%d",ans);
	return 0;
} 


Question 04 [ACP2513 Sudoku]
题面就是个简简单单的数独
主体还是dfs+回溯
然而细节...

01 二进制优化
用一个九位无符号整数表示数独中哪几个数可以选择
example (000110010) 表示 在该范围内2,5,6三个数字可以选择而其他数字不可以
而要把行列和单个方格的信息结合起来
只需要使用与的位运算即可 
将信息取出可以使用 lowbit 和预处理的 log 数组结合实现
为了实现第二步我们还需要预处理出每个二进制数之中数字一的个数 (即限制数)
至于用数组......我只能说你可以试试

02 Basic 01 顺序优化
容易知道如果当前一步限制多的更容易被选出 
而如果有 9 个限制即证明当前分支已经无解
可以直接 return 掉(Basic 02 可行性剪枝)
同时需要将 DFS 设为 bool 类型记录是否匹配成功
我们找到限制最多的位置
对其进行讨论 DFS 即为更优选择

03 回溯
这本来并不难,当然在这道题里就是另一说了
我们记录的限制只有行,列和方格3种 (不要记录单个方格! 回溯直接就把你 taskkill 了!)
很明显一行一列或者一个方格不会出现两个相同的数
所以在放置/删除数的时候修改状态值
只需要暴力的加或者减即可

04 输入
本题在 Accoders 上抽象的读入方式令人暖心
必须特殊处理

接下来的就是开始码......

Code
#include<bits/stdc++.h>
using namespace std;
const int N=10,sqrtN=4,squN=82,Size=9,Max=511;
int mp[N][N],one[520],line[N],colume[N],square[sqrtN][sqrtN];
int logBin(int x){
    if(x==1)return 1;
    if(x==2)return 2;
    if(x==4)return 3;
    if(x==8)return 4;
    if(x==16)return 5;
    if(x==32)return 6;
    if(x==64)return 7;
    if(x==128)return 8;
    if(x==256)return 9;
    puts("Shit!");
    return -1;
}
void place(int value,int x,int y,int on){
    if(abs(on)!=1){
        puts("Illegal value!");
        return;
    }
    if(on==1) mp[x][y]=value; else mp[x][y]=-1;
    line[x]-=on*(1<<(value-1));
    colume[y]-=on*(1<<(value-1));
    square[(x-1)/3+1][(y-1)/3+1]-=on*(1<<(value-1));
}
int lowbit(int x){
    return x&-x;
}
bool dfs(int todo){
    if(todo==0){
        for(int i=1;i<=9;i++)for(int j=1;j<=9;j++)printf("%d",mp[i][j]);
        puts("");
        return true;
    }
    int minx=-1,miny=-1,minnum=10,lim,key;
    for(int i=1;i<=9;i++)for(int j=1;j<=9;j++){
    	if(mp[i][j]!=-1)continue;
        lim=line[i]&colume[j]&square[(i-1)/3+1][(j-1)/3+1];
        if(one[lim]==0)return false;
        if(one[lim]<minnum)minnum=one[lim],minx=i,miny=j,key=lim;
    }
    while(key){
        place(logBin(lowbit(key)),minx,miny,1);
        if(dfs(todo-1))return true;
        place(logBin(lowbit(key)),minx,miny,-1);
        key-=lowbit(key);
    }
    return false;
}
int main(){
    int todo;
    for(int i=0,tmp;i<=Max;i++){
        tmp=i;
        while(tmp){
            if(tmp&1)one[i]++;
            tmp>>=1;
        }
    }
    char input_data[squN];
    while(true){
        for(int i=1;i<=9;i++)line[i]=Max,colume[i]=Max;
        for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)square[i][j]=Max;
        todo=0;
        scanf("%s",input_data);
        if(input_data[0]=='e')return 0;
        for(int i=0;i<=80;i++){
            if(isdigit(input_data[i])){
                place(input_data[i]-'0',i/9+1,i%9+1,1);//place num
            }else{
                ++todo;
                mp[i/9+1][i%9+1]=-1;
            }
        }
        dfs(todo);
    }
    return 0;
}