devbox
小丑西瓜9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

DFS合集（蓝桥杯C/C++）（随时更新，更新时间：2023.3.6）_蓝桥杯c++dfs

作者：小丑西瓜9 | 2024-03-17 02:46:07

赞

踩

蓝桥杯c++dfs

目录

1  数的全排列（模板）

2  n皇后问题

3  2n皇后问题

4  车的放置

5  粘木棍

6  24点

7  五星填数

1  数的全排列（模板）

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int a[10]={1,2,3,4,5,6,7,8,9,10};
  5. int b[10];
  6. bool vis[10];
  7.  
  8. void dfs(int s)
  9. {
  10. 	if(s==6)
  11. 	{
  12. 		for(int i=0;i<6;i++)
  13. 		{
  14. 			cout<<b[i]<<' '; 
  15. 		}
  16. 		cout<<endl;
  17. 		return;
  18. 	}
  19. 	for(int i=0;i<6;i++)
  20. 	{
  21. 		if(!vis[i])
  22. 		{
  23. 			vis[i]=true;
  24. 			b[s]=a[i];
  25. 			dfs(s+1);
  26. 			vis[i]=false;
  27. 		}
  28. 	}
  29. } 
  30.  
  31. int main()
  32. {
  33. 	dfs(0);
  34. 	return 0;
  35. }

2  n皇后问题

特点：充分运用全排列知识，每一行只能放一个皇后，全排列保证每一列只能出现一个皇后，斜线再进行后续处理

3  2n皇后问题

特点：在n皇后的基础上需要再次运用全排列，属于嵌套搜索

原题：

2n皇后问题（蓝桥杯基础练习C/C++）_菜只因C的博客-CSDN博客_2n皇后问题蓝桥杯2n皇后问题（蓝桥杯基础练习C/C++）https://blog.csdn.net/m0_71934846/article/details/128772257代码：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int mp[9][9];//初始化地图 
  5. bool visblack[9];//黑皇后是否用到 
  6. bool viswhite[9];//白皇后是否用到 
  7. int black[9],white[9];//皇后放到第几列 *解释1* 
  8. int ans;//答案 
  9. int cnt,cnt1,cnt2,n,jishu[30],temp;//计数用 
  10. int j,i;//循环变量 
  11. void dfswhite(int p)//后放 
  12. {
  13. 	if(p==n+1)//设置边界 
  14. 	{
  15. 		cnt=0,cnt1=0,cnt2=0,temp=0;//计数用的变量必须归零 
  16. 		memset(jishu,0,sizeof(jishu));
  17. 		for(int j=1;j<=n;j++)
  18. 		{
  19. 			if(mp[j][white[j]]==1)//检测该位置是否能放皇后 
  20. 			{
  21. 				cnt++;
  22. 			}
  23. 			for(int k=0;k<=n-1;k++)//*解释2* *解释3* 
  24. 			{
  25. 				if(j+white[j]==n+1+k)  jishu[k]++;//0ton-1
  26. 			}
  27. 			for(int k=1;k<=n-1;k++)
  28. 			{
  29. 				if(j+white[j]==n+1-k)  jishu[n+k-1]++;//nto2n-2
  30. 			}
  31. 			for(int k=0;k<=n-1;k++)
  32. 			{
  33. 				if(white[j]==j+k)  jishu[2*n-1+k]++;//2n-1to3n-1
  34. 			}
  35. 			for(int k=1;k<=n-1;k++)
  36. 			{
  37. 				if(white[j]==j-k)  jishu[3*n+k-2]++;//3nto4n-1
  38. 			}
  39. 		}
  40. 		/*for(int j=1;j<=50;j++)//测试用 
  41. 		{
  42. 			cout<<jishu[j]<<' ';
  43. 		}
  44. 		cout<<endl;*/
  45. 		for(int k=0;k<=29;k++)
  46. 		{
  47. 			if(jishu[k]>=2)  cnt--;
  48. 		}
  49. 		if(cnt==n)
  50. 		{
  51. 			/*for(int j=1;j<=n;j++)
  52. 			{
  53. 				cout<<"bai"<<white[j]<<' ';
  54. 			}
  55. 			cout<<endl;*/
  56. 			ans++;
  57. 		}  
  58. 		return;
  59. 	}
  60. 	
  61. 	for(int i=1;i<=n;i++)//dfs全排列*解释4* 
  62. 	{
  63. 		if(!viswhite[i])
  64. 		{
  65. 			viswhite[i]=true;
  66. 			white[p]=i;
  67. 			dfswhite(p+1);
  68. 			viswhite[i]=false;
  69. 		}
  70. 	}
  71. 	return;
  72. }
  73.  
  74. void dfsblack(int s)//先放 
  75. {
  76. 	if(s==n+1)
  77. 	{
  78. 		cnt=0,cnt1=0,cnt2=0,temp=0;
  79. 		memset(jishu,0,sizeof(jishu));
  80. 		for(int i=1;i<=n;i++)
  81. 		{
  82. 			if(mp[i][black[i]]==1)
  83. 			{
  84. 				cnt++;
  85. 			} 
  86. 			for(int k=0;k<=n-1;k++)
  87. 			{
  88. 				if(i+black[i]==n+1+k)  jishu[k]++;
  89. 			}
  90. 			for(int k=1;k<=n-1;k++)
  91. 			{
  92. 				if(i+black[i]==n+1-k)  jishu[n+k-1]++;
  93. 			}
  94. 			for(int k=0;k<=n-1;k++)
  95. 			{
  96. 				if(black[i]==i+k)  jishu[2*n-1+k]++;
  97. 			}
  98. 			for(int k=1;k<=n-1;k++)
  99. 			{
  100. 				if(black[i]==i-k)  jishu[3*n+k-2]++;
  101. 			} 
  102. 		}
  103. 		/*for(int j=1;j<=50;j++)
  104. 		{
  105. 			cout<<jishu[j]<<' ';
  106. 		}
  107. 		cout<<endl;*/
  108. 		for(int k=0;k<=29;k++)
  109. 		{
  110. 			if(jishu[k]>=2)  cnt--;
  111. 		}
  112. 		if(cnt==n)
  113. 		{
  114. 			/*for(int i=1;i<=n;i++)
  115. 			{
  116. 				cout<<"hei"<<black[i]<<' ';
  117. 			}
  118. 			cout<<endl;*/
  119. 			for(int i=1;i<=n;i++)
  120. 			{
  121. 				mp[i][black[i]]=0;
  122. 			}
  123. 			//cout<<"开始"<<endl;
  124. 			dfswhite(1);
  125. 			//cout<<"结束"<<endl;
  126. 			for(int i=1;i<=n;i++)
  127. 			{
  128. 				mp[i][black[i]]=1;
  129. 			}
  130. 		}  
  131. 		return;
  132. 	}
  133. 	
  134. 	for(int i=1;i<=n;i++)
  135. 	{
  136. 		if(!visblack[i])
  137. 		{
  138. 			visblack[i]=true;
  139. 			black[s]=i;
  140. 			dfsblack(s+1);
  141. 			visblack[i]=false;
  142. 		}
  143. 	}
  144. 	return;
  145. }
  146.  
  147. int main()
  148. {
  149. 	cin>>n;
  150. 	for(int i=1;i<=n;i++)
  151. 	{
  152. 		for(int j=1;j<=n;j++)
  153. 		{
  154. 			cin>>mp[i][j];
  155. 		}
  156. 	}
  157. 	dfsblack(1);
  158. 	cout<<ans;
  159. 	return 0;
  160. }

4  车的放置

特点：在n皇后问题上进行修改，不限制放置数量，需要搜索次数更多

原题：

车的放置（蓝桥杯算法训练C/C++）_菜只因C的博客-CSDN博客车的放置（蓝桥杯算法训练C/C++）https://blog.csdn.net/m0_71934846/article/details/128876478?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22128876478%22%2C%22source%22%3A%22m0_71934846%22%7D代码：

  1. #include  <bits/stdc++.h>
  2. using namespace std;
  3. int N;
  4. long long ans=0; 
  5. bool vis[10]; 
  6. void dfs(int s)
  7. {
  8.     if(s>N)
  9. 	{
  10. 		ans++;
  11. 		return ;
  12. 	} 
  13.     for(int i=1;i<=N;i++)
  14.     {
  15.     	if(!vis[i]) 
  16.         {
  17.             vis[i]=true; 
  18.     
  19.             dfs(s+1); 
  20.             vis[i]=false; 
  21.         }
  22. 	}  
  23.     dfs(s+1); //不一定从第s行开始放（即第s行没有也可以），从s+1行开始放也可以
  24. }
  25. int main()
  26. {
  27.     cin>>N;
  28.     dfs(1);
  29.     cout<<ans;
  30.     return 0;
  31. }
  32.

5  粘木棍

特点：把n个数据放入m个位置中加和（其中n>m）

原题：

粘木棍（蓝桥杯算法训练C/C++）_菜只因C的博客-CSDN博客粘木棍（蓝桥杯算法训练C/C++）https://blog.csdn.net/m0_71934846/article/details/128876620?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22128876620%22%2C%22source%22%3A%22m0_71934846%22%7D代码：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int a[10];
  4. int n,m;
  5. int ans=INT_MAX;
  6. bool vis[10];
  7. int sum[10];
  8. void dfs(int k)
  9. {
  10. 	if(k>=n+1)
  11. 	{
  12. 		int maxsum=0,minsum=INT_MAX;
  13. 		for(int i=1;i<=m;i++)
  14. 		{
  15. 			maxsum=max(maxsum,sum[i]);
  16. 			minsum=min(minsum,sum[i]);
  17. 		}
  18. 		ans=min(maxsum-minsum,ans);
  19. 		return ;
  20. 	}
  21. 	for(int i=k;i<=n;i++)   //注意这个地方是从k开始的，防止重复计算，剪枝，否则得90分 
  22. 	{
  23. 		if(!vis[i])
  24. 		{
  25. 			vis[i]=true;       
  26. 			for(int j=1;j<=m;j++)
  27. 			{
  28. 				sum[j]+=a[i];
  29. 				dfs(k+1);
  30. 				sum[j]-=a[i]; 
  31. 			}
  32. 			vis[i]=false;
  33. 		}
  34. 	} 
  35. }
  36. int main()
  37. {
  38. 	cin>>n>>m;
  39. 	for(int i=1;i<=n;i++)
  40. 	{
  41. 		cin>>a[i];
  42. 	}
  43. 	dfs(1);
  44. 	cout<<ans;
  45. 	return 0;
  46.  }

6  24点

特点：需要两个数两个数搜索

原题：

https://blog.csdn.net/m0_71934846/article/details/128878572https://blog.csdn.net/m0_71934846/article/details/128878572代码：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n;					
  5. int nums[4];			
  6. int ans;				
  7.  
  8. void f(int nums[], int n)
  9. {
  10.  
  11. 	if(n==1)//边界 
  12. 	{
  13. 		if(nums[n-1]<=24)
  14. 		{
  15. 			ans=max(ans,nums[n-1]);
  16. 		}
  17. 		return ;
  18. 	}
  19. 	
  20. 	//遍历两个数的组合 
  21. 	for(int i=0; i<n-1; i++)
  22. 	{
  23. 		for(int j=i+1; j<n; j++)
  24. 		{
  25. 			int a=nums[i], b=nums[j];
  26. 			
  27. 			nums[j] = a + b;//不断计算当前值放给nums[j]	
  28. 			nums[i] = nums[n-1];//不断把未计算的值放给nums[i] 
  29. 			f(nums, n-1);
  30. 			
  31. 			nums[j] = a * b;
  32. 			nums[i] = nums[n-1];
  33. 			f(nums, n-1);
  34. 			
  35. 			nums[j] = a - b;		
  36. 			nums[i] = nums[n-1];
  37. 			f(nums, n-1);
  38. 			
  39. 			nums[j] = b - a;
  40. 			nums[i] = nums[n-1];
  41. 			f(nums, n-1);
  42. 			
  43. 			if(b!=0 && a%b==0)
  44. 			{		
  45. 				nums[j] = a / b;
  46. 				nums[i] = nums[n-1];
  47. 				f(nums, n-1);
  48. 			}
  49. 			
  50. 			if(a!=0 && b%a==0)
  51. 			{
  52. 				nums[j] = b / a;
  53. 				nums[i] = nums[n-1];
  54. 				f(nums, n-1);
  55. 			}
  56. 			
  57. 			nums[i] = a;//回溯 
  58. 			nums[j] = b;
  59. 		}
  60. 	} 
  61. }
  62.  
  63. int main()
  64. {	
  65. 	cin>>n;
  66. 	for(int i=0; i<n; i++)
  67. 	{
  68. 		for(int j=0; j<4; j++)
  69. 		{
  70. 			cin >> nums[j];
  71. 		}
  72. 		ans = 0;		
  73. 		f(nums, 4);
  74. 		cout<<ans<<endl;
  75. 	}
  76. 	return 0; 
  77. }

7  五星填数

特点：全排列+筛选

原题:https://blog.csdn.net/m0_71934846/article/details/129336863?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22129336863%22%2C%22source%22%3A%22m0_71934846%22%7Dicon-default.png?t=N176https://blog.csdn.net/m0_71934846/article/details/129336863?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22129336863%22%2C%22source%22%3A%22m0_71934846%22%7D代码：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int a[10]={1,2,3,4,5,6,8,9,10,12};
  4. int b[10];
  5. bool vis[10];
  6. int ans;
  7. void dfs(int s,int step)
  8. {
  9. 	if(s==step)
  10. 	{
  11. 		/*for(int i=0;i<step;i++)
  12. 		{
  13. 			printf("%d ",b[i]);
  14. 		}
  15. 		printf("\n");*/
  16. 		int t=b[0]+b[2]+b[5]+b[8];
  17. 		if(t==b[0]+b[3]+b[6]+b[9]&&t==b[1]+b[2]+b[3]+b[4]&&t==b[1]+b[5]+b[7]+b[9]&&t==b[4]+b[6]+b[7]+b[8]) ans++;
  18. 	}
  19. 	for(int i=0;i<10;i++)
  20. 	{
  21. 		if(!vis[i])
  22. 		{
  23. 			vis[i]=true;
  24. 			b[s]=a[i];
  25. 			dfs(s+1,step);
  26. 			vis[i]=false;
  27. 		}
  28. 	}
  29. }
  30.  
  31. int main()
  32. {
  33. 	dfs(0,10);
  34. 	printf("%d",ans/10);
  35. 	return 0;
  36. }

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

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号