抽象形式的dfs

 1 #include<iostream>
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 int n,m,k;
 5 int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};
 6 int price[35];
 7 int vis[35];
 8 int flag=0;
 9 void dfs(int p,int c,int index)
10 {
11     //cout<<p<<" "<<c<<" "<<index<<endl;
12     if(index>=n) return;
13     if(p+price[index]==m&&c+1==k)
14     {
15         flag=1;
16         return;
17     }k
18     if(c+1>k)
19     {
20         return;
21     }
22     dfs(p+price[index],c+1,index+1);
23     //cout<<"here"<<endl;
24     dfs(p,c,index+1);
25 }
26 int main()
27 {
28     ios::sync_with_stdio(false);
29     cin>>m>>n>>k;
30     memset(vis,0,sizeof(vis));
31     for(int i=0; i<n; i++)
32     {
33         cin>>price[i];
34     }
35     dfs(0,0,0);
36     if(flag)
37         cout<<"Yes"<<endl;
38     else
39         cout<<"No"<<endl;
40     return 0;
41 }

 1 #include<iostream>
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 int n,m,k;
 5 int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};
 6 int len[25];
 7 int vis[25];
 8 int flag=0;
 9 int sum=0;
10 int each=0;
11 int countt=0;
12 void dfs(int len_a,int len_b,int len_c,int index)
13 {
14     if(flag) return;
15     if(len_a==len_b&&len_a==each&&len_c==each)
16     {
17         //cout<<len_a<<" "<<len_b<<" "<<each<<endl;
18         flag=1;
19         return;
20     }
21     if(index>n-1) return;
22     if(len_a>each||len_b>each||len_c>each) return;
23     dfs(len_a+len[index],len_b,len_c,index+1);
24     if(flag) return;
25     dfs(len_a,len_b+len[index],len_c,index+1);
26     if(flag) return;
27     dfs(len_a,len_b,len_c+len[index],index+1);
28 }
29 int main()
30 {
31     ios::sync_with_stdio(false);
32     cin>>n;
33     memset(vis,0,sizeof(vis));
34     for(int i=0; i<n; i++)
35     {
36         cin>>len[i];
37         sum+=len[i];
38     }
39     if(sum%3!=0)
40     {
41         cout<<"no"<<endl;
42     }
43     else
44     {
45         each=sum/3;
46         dfs(0,0,0,0);
47         if(flag)
48             cout<<"yes"<<endl;
49         else
50             cout<<"no"<<endl;
51     }
52     return 0;
53 }

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int chess[8][8];
 4 int col[8];
 5 int maxx=0;
 6 int sum=0;
 7 int cnt=0;
 8 int n=8;
 9 void print()
10 {
11     for(int i=0; i<n; ++i)
12     {
13         for(int j=0; j<n; ++j)
14         {
15             if(j == col[i]) cout<<"1 ";
16             else cout<<"0 ";
17         }
18         cout<<endl;
19     }
20 }
21 void dfs(int row)
22 {
23     if(row==n)
24     {
25         for(int i=0;i<n;i++)
26         {
27             sum+=chess[i][col[i]];
28         }
29         if(maxx<sum)
30         {
31             maxx=sum;
32         }
33         sum=0;
34         //print();
35         //++cnt;
36         return;
37     }
38     for(int i=0;i<n;i++)
39     {
40         col[row]=i;
41         int ok=1;
42         for(int j=0;j<row;j++)
43         {
44             if(col[row]==col[j]||row-j==col[row]-col[j]||row-j==col[j]-col[row])
45             {
46                 ok=0;
47                 break;
48             }
49         }
50         if(ok) dfs(row+1);
51     }
52 }
53 int main()
54 {
55 
56     for(int i=0; i<n; i++)
57     {
58         for(int j=0; j<n; j++)
59         {
60             cin>>chess[i][j];
61         }
62     }
63     dfs(0);
64     cout<<maxx<<endl;
65     return 0;
66 }

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n;
 4 int t[10][10];
 5 int arr[10];
 6 int sum=0;
 7 int minn=1000000;
 8 int main()
 9 {
10     cin>>n;
11     for(int i=0;i<n;i++)
12     {
13         for(int j=0;j<n;j++)
14         {
15             //第i项工作由j号员工完成所需要的时间
16             cin>>t[i][j];
17         }
18     }
19 
20     for(int i=0;i<n;i++)
21     {
22         arr[i]=i;
23     }
24 
25     do{
26         for(int i=0;i<n;i++)
27         {
28             sum+=t[i][arr[i]];
29             //cout<<arr[i]<<" ";
30         }
31         if(minn>sum)
32         {
33             minn=sum;
34         }
35         sum=0;
36     }while(std::next_permutation(arr,arr+n));//获取所有全排列
37 
38     cout<<minn<<endl;
39     return 0;
40 }