DFS深搜

目录

dfs深度优先搜索：

通用模板：

e.g. 1：

e.g. 2：

e.g. 3：

推荐题目：

剪枝

P1219 [USACO1.5] 八皇后 Checker Challenge

题面

输入格式

输出格式

思考

AC代码

---

dfs深度优先搜索：

dfs是一条路走到黑，沿着一条路径一直向下搜索，直到没有下一步，再通过return回溯到上一个节点继续向下搜索(记得要回溯)。

通用模板：

int check(参数)

{

? ? ? ? if(满足条件)

? ? ? ? ? ? ? ? return 1;

? ? ? ? return 0;

}

void dfs(int step)

{

? ? ? ? 判断边界；

? ? ? ? {

? ? ? ? ? ? ? ? 相应操作；

????????}

? ? ? ? 尝试每一种可能；

? ? ? ? {

? ? ? ? ? ? ? ? 满足check条件；

? ? ? ? ? ? ? ? 标记；

? ? ? ? ? ? ? ? dfs(step+1);

? ? ? ? ? ? ? ? return回溯；

????????}

}

在做题时可以利用递归搜索树来帮助思考。

e.g. 1：

输入n,从1到n中选数，输出所有可能

3

3

2

2 3

1

1 3

1 2

1 2 3

有1，2，3共3个数，给出_ _ _三个位置用于存放三个数字，用选或不选两种状态来判断并进行搜索。

#include<iostream>
using namespace std;
int n;
int a[100];
void dfs(int x)
{
    if(x>n)
    {
        for(int i=1;i<=n;i++)
        {
            if(a[i]==1)
            {
                cout<<i;
            }
        }
        cout<<endl;
        return;
    }
    a[x]=1;
    dfs(x+1);
    a[x]=0;

    a[x]=2;
    dfs(x+1);
    a[x]=0;
}    
int main()
{
    cin>>n;
    dfs(1);
    return;
}

e.g. 2：

已知?n?个整数?x1?,x2?,?,xn?，以及1个整数?k(k<n）。从?n?个整数中任选?k?个整数相加，可分别得到一系列的和。例如当?n=4，k=3，4?个整数分别为?3,7,12,19?时，可得全部的组合与它们的和为：

3+7+12=22

3+7+19=29

7+12+19=38

3+12+19=34

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：3+7+19=29。

4 3

3 7 12 19

1

#include<iostream>
using namespace std;
int n,k;
int a[100];
int b[100];
int ans=0;
bool prime(int s)//素数判断
{
	if(s<2) return false;
	for(int i=2;i<=s/i;i++)
	{
		if(s%i==0) return false;
	}
	return true;
}
void dfs(int x,int y)
{

	if(x>k)
	{
		int s=0;
		for(int i=1;i<=k;i++)
		{
			s+=a[i];//s,计算3个数的和
		}
		if(prime(s))//判断
		{
			ans++;//判断成功，ans+1，记录素数个数
		}
		return;
	}
	for(int i=y;i<=n;i++)
	{
		a[x]=b[i];//如果当前数已经放过
		dfs(x+1,i+1);//继续向下搜索
		a[x]=0;
	}
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&b[i]);//存放数
	}
	dfs(1,1);
	printf("%d",ans);
	return 0;
}

e.g. 3：

猪猪 Hanke 特别喜欢吃烤鸡，Hanke 吃鸡很特别，为什么特别呢？因为他有10种配料，每种配料可以放1到3克，任意烤鸡的美味程度为所有配料质量之和。

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

输入格式

一个正整数?n，表示美味程度。

输出格式

第一行，方案总数。

第二行至结束,10个数，表示每种配料所放的质量，按字典序排列。

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

11

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 n;
int a[11];
int b[60000][11];//3的10次方种方案
int ans=0;
void dfs(int x,int sum)
{
	if(sum>n)
	return;
	if(x>10)
	{
		if(sum==n)
		{
			ans++;
			for(int i=1;i<=10;i++)
			{
				b[ans][i]=a[i];
			}
		}
		return;
	}
	for(int i=1;i<=3;i++)
	{
		a[x]=i;
		dfs(x+1,sum+i);
		a[x]=0;
	}
} 
int main()
{
	cin>>n;
	dfs(1,0);
	printf("%d\n",ans);
	for(int i=1;i<=ans;i++)
	{
		for(int j=1;j<=10;j++)
		{
			printf("%d ",b[i][j]);
		}
		cout<<endl;
	}
	return 0; 
}

推荐题目：

洛谷：1088，1149，2036，1135；这几个题目难度不大，可以练练手。

剪枝

DFS是一种暴力算法，本质上是将每一种方法枚举出来再进行筛选，因此在处理大规模数据时常常会超时，所以要进行剪枝，将一些不必要的路径丢掉。

剪枝分为很多种，在做题时我们需要根据具体题目来进行不同的剪枝。

P1219 [USACO1.5] 八皇后 Checker Challenge

这是一道非常不错的剪枝题，推荐你们做一下。

题面

一个如下的?6×6?的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。

上面的布局可以用序列?2?4?6?1?3?5?来描述，第?i?个数字表示在第?i?行的相应位置有一个棋子，如下：

行号?1?2?3?4?5?61?2?3?4?5?6

列号?2?4?6?1?3?52?4?6?1?3?5

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前?3?个解。最后一行是解的总个数。

输入格式

一行一个正整数?n，表示棋盘是 n×n?大小的。

输出格式

前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

注意：对于 100%?的数据，6≤n≤13。

6

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

13

1 3 5 2 9 12 10 13 4 6 8 11 7
1 3 5 7 9 11 13 2 4 6 8 10 12
1 3 5 7 12 10 13 6 4 2 8 11 9
73712

思考

对于这一道题如果用普通的DFS肯定会超时，最多有13*13=169个格子，而每一个格子有2种方案，数据量很大，所以要剪枝。

画图观察可以看出：“/”这样的对角线x+y为定值；“\”这样的对角线x-y为定值。

可以用这个规律对对角线进行特判，但是这样还是不够。

我们可以一整行一整行的进行搜索，这样最复杂的情况就只有13个格子，每个格子两种可能，数据量大大减少。

AC代码

#include<iostream>
using namespace std;  
int n, ans, h[15], l[15], a[30], b[30]; 
void dfs(int x)  
{  
    if(x == n + 1)  // 如果当前位置等于总位置数加1，说明已经遍历完所有位置  
    {  
        ans++;  // 答案加1，表示找到了一个有效的解决方案  
        if(ans <= 3)  // 如果找到的解决方案数量小于或等于3  
        {  
            for(int i = 1; i <= n; i++)  // 打印当前解决方案  
                printf("%d ", h[i]);  
            printf("\n");  
        }  
        return;  // 结束当前递归调用  
    }  
    for(int i = 1; i <= n; i++)  // 遍历所有可能的值  
    {  
        if(l[i] == 0 && a[x - i + n] == 0 && b[x + i] == 0)  // 如果当前位置的值、它的逆位置的值以及它左右两边的位置都为0  
        {  
            l[i] = a[x - i + n] = b[x + i] = 1;  // 将当前位置的值、它的逆位置的值以及它左右两边的位置都设为1，表示已经使用过  
            h[x] = i;  // 将当前位置的值设为当前遍历到的值  
            dfs(x + 1);  // 递归调用，移动到下一个位置继续搜索  
            h[x] = l[i] = a[x - i + n] = b[x + i] = 0;  // 回溯，将当前位置的值、它的逆位置的值以及它左右两边的位置都设为0，表示可以再次使用  
        }  
    }  
}  
int main()  
{  
    scanf("%d", &n);
    dfs(1);  // 从位置1开始进行dfs  
    printf("%d\n", ans);  
    return 0;   
}