c++dfs代替枚举题解

深度优先搜索（depth-first-search）简称 dfs，应该算是应用得最广泛的搜索算法，也是竞赛中经常考察的一个难点。dfs 按照深度优先的方式搜索，通俗的说就是一条路走到黑。dfs 是一种穷举的手段，实际上就是把所有的可行方案列举出来，不断去试探，直到找到问题的解，其过程是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

dfs 是一种搜索算法，dfs 一般的实现方法是借助递归。

void dfs(int deep) {
    if (到达边界) {
      // 做一些处理后返回
    } else {
        for(所有可能的选择) {
            dfs(deep + 1);
        }
    }
}

上面是 dfs 的一般的写法。

dfs 和递归的区别是，dfs 是一种算法，注重的是思想，而递归是编程语言的一种写法。我们通过递归的写法来实现 dfs。 在之前我们讲到的递归每个节点最多只有 2 个分支，而在接下来的 dfs 中，每个节点可以扩展出很多个分支。

例题洛谷P2089

题目背景

猪猪hanke得到了一只鸡

题目描述

猪猪Hanke特别喜欢吃烤鸡（本是同畜牲，相煎何太急！）Hanke吃鸡很特别，为什么特别呢？因为他有10种配料（芥末、孜然等），每种配料可以放1—3克，任意烤鸡的美味程度为所有配料质量之和

现在，Hanke想要知道，如果给你一个美味程度，请输出这10种配料的所有搭配方案

输入输出格式

输入格式：

一行,n<=5000

输出格式：

第一行，方案总数

第二行至结束，10个数，表示每种配料所放的质量

按字典序排列。

如果没有符合要求的方法，就只要在第一行输出一个“0”

输入输出样例

输入样例#1：复制

11

输出样例#1：复制

10
1 1 1 1 1 1 1 1 1 2 
1 1 1 1 1 1 1 1 2 1 
1 1 1 1 1 1 1 2 1 1 
1 1 1 1 1 1 2 1 1 1 
1 1 1 1 1 2 1 1 1 1 
1 1 1 1 2 1 1 1 1 1 
1 1 1 2 1 1 1 1 1 1 
1 1 2 1 1 1 1 1 1 1 
1 2 1 1 1 1 1 1 1 1 
2 1 1 1 1 1 1 1 1 1 

解（枚举法）直接枚举出所有情况，遇到满足条件的情况就直接进行记录和存储：

#include<iostream>
using namespace std;
int map[10000][10];
int main(){
    int n,length=0;
    cin>>n;
    int a,b,c,d,e,f,g,h,j,k;
    for( a=1;a<=3;a++)
    for( b=1;b<=3;b++)
    for(c=1;c<=3;c++)
    for(d=1;d<=3;d++)
    for(e=1;e<=3;e++)
    for(f=1;f<=3;f++)
    for(g=1;g<=3;g++)
    for(h=1;h<=3;h++)
    for(j=1;j<=3;j++)
    for(k=1;k<=3;k++)
        if((a+b+c+d+e+f+g+h+j+k)==n){
            map[length][0]=a,map[length][1]=b;
            map[length][2]=c,map[length][3]=d;
            map[length][4]=e,map[length][5]=f;
            map[length][6]=g,map[length][7]=h;
            map[length][8]=j;map[length][9]=k;
            length++;
        }
    cout<<length<<endl;
    for(int i=0;i<length;i++){
        for(int j=0;j<10;j++)
            cout<<map[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}

解2（深度优先搜索）从第一层开始及第一个数组元素，记录当前数组和。一直往下深搜，当最后达到临界时进行条件判断，满足条件的记录数据和存储数据。不满足的就return返回上一层。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,a[10],map[10000][10],ans=0;
void dfs(int deap,int nowsum){
	if(deap>10){
		if(a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7]+a[8]+a[9]+a[10]==n){
			for(int i=0;i<10;i++){
				map[ans][i]=a[i+1];
			}
			ans++;
		}
		return ;
	}
	for(int i=1;i<=3;i++){
		if(nowsum+i>n)
			break;
		a[deap]=i;
		dfs(deap+1,nowsum+i);
	}
}
int main(){
	cin>>n;
	memset(a,0,sizeof(a));
	dfs(1,0);
	cout<<ans<<endl;
	for(int i=0;i<ans;i++){
		for(int j=0;j<10;j++)
			cout<<map[i][j]<<" ";
		cout<<endl;
	}
	return 0;
}