经典DFS问题实践

八皇后问题：

 1 //八皇后问题  经典的DFS问题实践
 2 #include<iostream>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstdio>
 6 using namespace std;
 7 int mat[8][8];
 8 int ans=0;
 9 bool check(int row,int col)//最终检查满足要求，则return 1
10 {
11     for(int i=0;i<row;i++)
12     {
13         if(mat[i][col])
14             return false;
15         for(int j=0;j<8;j++)
16         {
17             //不能在同一条对角线上
18             if(mat[i][j])
19             {
20               if(fabs(i-row)-fabs(j-col)==0)
21                  return 0;
22               else
23                  continue;
24 
25             }
26         }
27     }
28     return 1;
29 }
30 int dfs(int row)
31 {
32     if(row>=8)
33     {
34         ans++;
35         for(int i=0;i<8;i++)
36         {
37             for(int j=0;j<8;j++)
38                cout<<mat[i][j]<<" ";
39             cout<<endl;
40         }
41         cout<<endl;
42     }
43     for(int col=0;col<8;col++)
44     {
45         if(check(row,col))
46         {
47             mat[row][col]=1;
48             dfs(row+1);
49             mat[row][col]=0;
50         }
51     }
52     return 0;
53 }
54 int main()
55 {
56     memset(mat,0,sizeof(mat));
57     dfs(0);
58     cout<<"一共有"<<ans<<"种解决方案"<<endl;
59 }

//最终结果显示一共有92种解决方案

部分和问题

给定整数a1、a2、.......an,判断是否可以从中选出若干个数，使他们的和恰好为k。

 1 //部分和问题
 2 #include <iostream>
 3 using namespace std;
 4 const int Maxn=10000;
 5 int a[Maxn];
 6 int n,k;
 7 bool dfs(int i,int sum){
 8     if(i==n) return sum==k;
 9     if(dfs(i+1,sum)) return true;//不加上a[i]的情况
10     if(dfs(i+1,sum+a[i])) return true;
11     return false;
12 
13 }
14 void solve()
15 {
16     if(dfs(0,0)) printf("yes!");
17     else printf("no!");
18 }
19 int main() {
20     cin>>n;
21     for(int i=0;i<n;i++){
22         cin>>a[i];
23     }
24     cin>>k;
25     solve();
26     return 0;
27 }