IT小白

这个屌丝很懒，什么也没留下！

热门标签

dfs经典例题（入门题）_c++ dfs入门基础题

作者：IT小白 | 2024-05-20 06:54:38

踩

c++ dfs入门基础题

再附上一篇DFS详解的，不明白DFS原理的同学可以看一看：https://blog.csdn.net/li_jeremy/article/details/83714298

以下是全网收集整理的和自己写的部分，绝对保证dfs轻松入门。

核心代码：

关于dfs参数问题，什么在变化，就把什么设置成参数。

    void dfs()//参数用来表示状态
    {
        if(到达终点状态)
        {
            ...//根据题意添加
            return;
        }
        if(越界或者是不合法状态)
            return;
        if(特殊状态)//剪枝
            return ;
        for(扩展方式)
        {
            if(扩展方式所达到状态合法)
            {
                修改操作;//根据题意来添加
                标记；
                dfs（）；
                (还原标记)；
                //是否还原标记根据题意
                //如果加上（还原标记）就是回溯法
            }

        }
    }

为什么有的时候得要标记，因为这可以防止打转现象的发生，你可以想象如果没有标记，你在迷宫围绕着某条路径打转

但有的时候需要标记却不需要还原标记，为何不需要还原标记，不还原的意义是防止下次递归时走到已走过的位置，还原是可以让下次递归可以在经过原先递归走过的路径，当然不可能和原先一模一样的路径

DFS全排列


#include<iostream>
using namespace std;
int n;
int book[10] = {0};
int a[10];
 
void dfs(int index)
{
	if(index == n)  //递归终止条件
	{
		for(int i = 0;i < n;++i)
		    cout << a[i];
	    cout << endl;
	    return ;
	}
	
	else
	{
		for(int i = 1;i <= n;++i)
		{
			if(!book[i])
			{
				book[i] = 1;//标记位
				a[index] = i;//把符合的数字保存到数组中
				dfs(index+1);
				a[index] = 0;
				book[i] = 0;//还原标记，以便回溯
			}
		}
	}
}
 
void init()
{
    for(int i = 0;i < 9;++i)
	    book[i] = 0;	
}
 
int main()
{
	
	while(cin >> n)	
	{
		dfs(0);
		init();
	}
	  
	return 0;
}

方格填数

如下的10个格子
+--+--+--+
| | | |
+--+--+--+--+
| | | | |
+--+--+--+--+
| | | |
+--+--+--+

（如果显示有问题，也可以参看【图1.jpg】）

填入0~9的数字。要求：连续的两个数字不能相邻。
（左右、上下、对角都算相邻）

一共有多少种可能的填数方案？

请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

这就是道全排列的变式题(因为数字是0-9，且填入到格子中)，因为它必须去检查所填的数字是否符合题目要求

思路：明显这是回溯题，可以用dfs做，当然你也可以套10个循环来做（TLE）

dfs的话这道题我们该如何进行递归，很明显这道题和全排列类似，所以我们可以一个方格一个方格来填空

由于题意要求连续的两个数字不能相邻

所以需要判断/左，上，左上，右上/，因为在你下面和右面的都还没填呢


#include<iostream>
#include<cmath>
#include<sstream>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue> 
#include<vector>
#include<algorithm>
using namespace std;
 
int ans = 0;
int dir[4][2] = {0,-1,-1,0,-1,-1,-1,1};
int book[10][10];
int a[10][10];
int vis[10];
 
/*左，上，左上，右上*/
bool check(int r,int c,int val)
{
    for(int k = 0;k < 4;++k)
	{
		int tr = r + dir[k][0];
		int tc = c + dir[k][1];
		if(tr < 1 || tc < 1 || tr > 3 || tc > 4)  continue;
		if(abs(a[tr][tc]-val) <= 1)  return false;
	}	
	
	return true;
}
 
void dfs(int row,int col)
{
	if(row == 3 && col == 4)
	{
		ans++;
		return ;
	}
	
	if(col == 5)
	{
		row += 1;
		col = 1;
	}
	
	
	
	for(int i = 0;i <= 9;++i)
    {
    	if(!book[row][col] && !vis[i] && check(row,col,i))
    	{
    		book[row][col] = 1;
    		vis[i] = 1;
    		a[row][col] = i;
    		dfs(row,col+1);
    		book[row][col] = 0;
    		vis[i] = 0;
    		a[row][col] = -2;
    	}
    	
    }
 
}
 
 
 
int main()
{
	for(int i = 0;i <= 5;++i)
	{
		for(int j = 0;j <= 9;++j)
		     a[i][j] = -2;
	}
	
	dfs(1,2);
	printf("%d\n",ans); 
	return 0;
}

寒假作业

现在小学的数学题目也不是那么好玩的。
看看这个寒假作业：

   □ + □ = □
   □ - □ = □
   □ × □ = □
   □ ÷ □ = □

   (如果显示不出来，可以参见【图1.jpg】)

每个方块代表1~13中的某一个数字，但不能重复。
比如：
6 + 7 = 13
9 - 8 = 1
3 * 4 = 12
10 / 2 = 5

以及：
7 + 6 = 13
9 - 8 = 1
3 * 4 = 12
10 / 2 = 5

就算两种解法。（加法，乘法交换律后算不同的方案）

你一共找到了多少种方案？

同样是全排列变式题，

思路：一个一个填，递归的参数应该是下标，用一维数组来存储，一种做法是，把加减乘除比较，不符合则返回上一层，还有一种做法，把12个位置先填满，在判断是否符合条件，这样做，时间复杂度更高


#include<iostream>
#include<cmath>
#include<sstream>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue> 
#include<vector>
#include<algorithm>
using namespace std;
 
int ans = 0;
 
int vis[10];
int a[13];
 
void dfs(int index)
{
	if(index == 13)
	{
	    //为何不能a[10]/a[11] && a[10] % a[11] == 0，   11/5 == 2吧
		if(a[10] == a[11]*a[12])
		{	
			ans++;			
		}
		return ; 
	} 
	
	//+
	if(index == 3)
	{
		if(!vis[a[1]+a[2]])
		{
		    vis[i] = 1;
			a[index] = i;
			dfs(index+1);
			vis[i] = 0;
			a[index] = 0;
         }
		     return ;
	}
	
	//-
	if(index == 7)
	{
		if(a[4]-a[5] != a[6])
			return ;
	}
	
	//*
	if(index == 10)
	{
		if(a[7]*a[8] != a[9])
			return ;
	}
	
	
	
	
	for(int i = 1;i <= 13;++i)
	{
		if(!vis[i])
		{
			vis[i] = 1;
			a[index] = i;
			dfs(index+1);
			vis[i] = 0;
			a[index] = 0;
		}
	}
 
}
 
 
 
int main()
{
	dfs(1); 
	printf("%d\n",ans);
	return 0;
}

剪邮票

如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。

请你计算，一共有多少种不同的剪取方法。

请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

思路：也是一道全排列变式题，只不过这里我们只截取其中5个格子判断是否连通，把选中的五个棋子的位置保存起来，如何判断连通呢？回溯即可


 
 
/*#include<iostream>
#include<cmath>
#include<sstream>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue> 
#include<vector>
#include<algorithm>
using namespace std;
int ans = 0;
int vis[9][9];
int dir[4][2] = {0,1,1,0,0,-1,-1,0};
int book[10000][5][5];
bool check(int count)
{
	if(count == 0)  return true;
	
	for(int k = 0;k < count;++k)
	{
		int flag = 1;
		for(int i = 1;i <= 3;++i)
        { 
	   	  for(int j = 1;j <= 4;++j)
	   	  {
   	  	        if(book[k][i][j] != vis[i][j])  flag = 0;
   	      }
       } 
       if(flag)
          return false;
	}
    
	return true;	  
}
void add(int a[][9],int count)
{
	    for(int i = 1;i <= 3;++i)
        { 
	   	  for(int j = 1;j <= 4;++j)
	   	  {
   	  	     book[count][i][j] = vis[i][j];
   	      }
       } 
}
void dfs(int r,int c,int sum)
{	
   if(sum == 4)
   {
   	   
   	   if(check(ans))
   	   {
		    add(vis,ans);
   	   	    ans++;
   	   	    
   	   	    for(int i = 1;i <= 3;++i)
            { 
		   	  for(int j = 1;j <= 4;++j)
		   	  {
	   	  	        printf("%d ",vis[i][j]);
	   	      }
	   	      printf("\n");
            } 
            
            printf("----------------------------------------------\n");
   	   }
   	       
   	   return ;
   }	
   
   for(int k = 0;k < 4;++k)
   {
   	    int tr = r + dir[k][0];
		int tc = c + dir[k][1];
		if(tr < 1 || tc < 1 || tr > 3 || tc > 4)  continue;
		if(!vis[tr][tc])
		{
			vis[tr][tc] = 1;
   	  	  	dfs(tr,tc,sum+1); 
   	  	  	vis[tr][tc] = 0;
		}
   }
 
} 
int main()
{
	for(int i = 1;i <= 3;++i)
    {
   	  for(int j = 1;j <= 4;++j)
   	  {
   	  	  if(!vis[i][j])
   	  	  {
   	  	  	  vis[i][j] = 1;
   	  	  	  dfs(i,j,0); 
   	  	  	  vis[i][j] = 0;
   	  	  	
   	  	  }
   	  }
    } 
	printf("%d\n",ans);
	return 0;
}*/
 
 
 
 
//别人的做法 
#include<iostream>
#include<cmath>
#include<sstream>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue> 
#include<vector>
#include<algorithm>
using namespace std;
 
int ans = 0;
 
int que[13][2];  //保存信息
int book[13][13];
int a[10];    
int vis[14];
int dir[4][2] = {0,1,1,0,0,-1,-1,0};
int flag = 1;
 
 
 
 
//通过回溯来判断 
int check(int x,int y)
{
 
	if(book[x][y] == 0) return 0;
	book[x][y] = 0;
		
	return 1+check(x-1,y)+check(x+1,y)+check(x,y-1)+check(x,y+1);	
}
 
 
void dfs(int sum,int last)
{	
   if(sum == 5)
   {
   	   
   	   memset(book,0,sizeof(book));
   	   //这里如何去判重
   	   
	   for(int i = 0;i < 5;++i)
	   {
	   	   book[que[a[i]][0]][que[a[i]][1]]= 1;
	   } 
	   
	   flag = 1;
	   if(check(que[last][0],que[last][1]) == 5)
	   {
	   	  ans++;
	   } 
	   
   	   return ;
   }	
   
   
   for(int i = last+1;i <= 12;++i)
   {
   	   if(!vis[i])
   	   {
   	   	  vis[i] = 1;
   	   	  a[sum] = i;
   	   	  dfs(sum+1,i);
   	   	  vis[i] = 0;
   	   	  a[sum] = -1;
   	   }
   }
   
} 
 
 
 
int main()
{
	int n = 1;
	for(int i = 1;i <= 3;++i)
    {
   	  for(int j = 1;j <= 4;++j)
   	  {
   	  	  //保存每个方格的横纵坐标 
   	  	  que[n][0] = i;
		  que[n++][1] = j; 
   	  }
    } 
	dfs(0,0);
	printf("%d\n",ans);
	return 0;
}

初学dfs：先做最最最基础的题： http://codeup.cn/contest.php?cid=100000608。

做完了，你就入门了（绝对没有比这更基础的题了）

然后再做下面的题：

题型分类：

写过这些入门题后，我们可以将DFS题分为两大类：

1 . 地图型：这种题型将地图输入，要求完成一定的任务。因为地图的存在。使得题意清楚形象化，容易理清搜索思路。

POJ 1031棋盘问题（类似八皇后问题）http://poj.org/problem?id=1321

        AOJ 869-迷宫(遍历地图，四向搜索)   https://blog.csdn.net/chen_yuazzy/article/details/73656668
        HDU 1035-Robot Motion(指定方向搜索，迷路（循环）判断)   http://acm.hdu.edu.cn/showproblem.php?pid=1035
        HDU 1045-Fire Net(check函数，回溯) http://acm.hdu.edu.cn/showproblem.php?pid=1045
        HDU 1010-Tempter of the Bone(奇偶剪枝，回溯) http://acm.hdu.edu.cn/showproblem.php?pid=1010

2 . 数据型：这种题型没有给定地图，一般是一串数字或字母，要求按照一定的任务解题。相对于地图型，这种题型较为抽象，需要在数据中进行搜索。数据以数组的形式存储，那么只要将数组也当作一张图来进行搜索就可以了。

        HDU 1016-Prime Ring Problem(回溯、素数筛)
        HDU 1258-Sum It Up(双重DFS递归，去重技巧)
        HDU 1015-Safecraker(回溯，字符处理)
        HDU 2676-Sudoku(抽象，回溯)

以下是一些DFS：

Sticks http://acm.hdu.edu.cn/showproblem.php?pid=1455

http://acm.hdu.edu.cn/showproblem.php?pid=1455

http://acm.hdu.edu.cn/showproblem.php?pid=2553

http://acm.hdu.edu.cn/showproblem.php?pid=1426

http://acm.hdu.edu.cn/showproblem.php?pid=1528

http://acm.hdu.edu.cn/showproblem.php?pid=1175

http://acm.hdu.edu.cn/showproblem.php?pid=1010

http://acm.hdu.edu.cn/showproblem.php?pid=1312

http://acm.hdu.edu.cn/showproblem.php?pid=1716

http://acm.hdu.edu.cn/showproblem.php?pid=5547

http://acm.hdu.edu.cn/showproblem.php?pid=1181

http://acm.hdu.edu.cn/showproblem.php?pid=5305

记忆化搜索（DFS+DP）：

http://acm.hdu.edu.cn/showproblem.php?pid=1978

http://acm.hdu.edu.cn/showproblem.php?pid=1078

http://acm.hdu.edu.cn/showproblem.php?pid=1428

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/596610