dfs小练【dfs】

1.前n个自然数的所有排列：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 int count=1,n;
 8 bool *b;
 9 int *a;
10 
11 void dfs(int);
12 
13 int main()
14 {
15     scanf("%d",&n);
16     b=new bool[n+1];
17     a=new int[n+1];
18     memset(b,0,n+1);//这里不能写sizeof(b)，b为变量指针
19     dfs(1);
20     return 0;
21 }
22 void dfs(int t)
23 {
24     for(int i=1;i<=n;i++)
25     {
26         if(b[i])    continue;
27         b[i]=1;
28         a[t]=i;
29         if(t==n)
30         {
31             printf("%d ",count++);
32             for(int j=1;j<=n;j++)   printf("%d",a[j]);
33             puts("");
34             b[i]=0;
35             return;
36         }
37         dfs(t+1);
38         b[i]=0;
39     }
40 }

View Code

2.迷宫是否有通路(dfs)：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 const int N=100;
 8 char mi_gong[N][N];
 9 bool b[N][N];
10 int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
11 int n,m,x1,x2,y1,y2;
12 bool bb;
13 
14 void Create();
15 bool CanMove(int x,int y);
16 void Dfs(int x,int y,int step);
17 
18 int main()
19 {
20     Create();
21     Dfs(x1,y1,0);
22     if(bb==0)   puts("小老鼠出不来，被憋死了。");
23     return 0;
24 }
25 void Create()
26 {
27     puts("请输入迷宫的行列数以及小老鼠的起点和终点，然后再输入迷宫每个格点，.代表可以走，#代表不可以走。");
28     scanf("%d%d%d%d%d%d",&n,&m,&x1,&y1,&x2,&y2);
29     for(int i=1;i<=n;i++)
30     {
31         getchar();
32         for(int j=1;j<=m;j++)
33         {
34             scanf("%c",&mi_gong[i][j]);
35         }
36     }
37 }
38 bool CanMove(int x,int y)
39 {
40     return x>0&&x<=n&&y>0&&y<=m&&mi_gong[x][y]=='.'&&b[x][y]==0;
41 }
42 void Dfs(int x,int y,int step)
43 {
44     if(bb)  return;
45     if(x==x2&&y==y2)
46     {
47         puts("小老鼠可以走出迷宫。");
48         bb=1;
49         return;
50     }
51     int tx,ty;
52     b[x][y]=1;
53     for(int i=0;i<4;i++)
54     {
55         tx=x+dx[i];
56         ty=y+dy[i];
57         if(CanMove(tx,ty))  Dfs(tx,ty,step+1);
58     }
59     b[x][y]=0;
60 }

View Code

3.给出n个正整数a1,a2,a3,...,an，和一个正整数k,问是否能从n个数中选出若干个数，使其和为k：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 bool ans;
 8 int n,k,*a,*s;
 9 void dfs(int i,int sum);
10 
11 int main()
12 {
13     scanf("%d%d",&n,&k);
14     a=new int[n];
15     s=new int[n];
16     for(int i=0;i<n;i++)    scanf("%d",&a[i]);
17     int s0=0;
18     for(int i=n-1;i>=0;i--) s0+=a[i],s[i]=s0;
19     dfs(0,0);
20     if(ans) cout<<"true";
21     return 0;
22 }
23 void dfs(int i,int sum)
24 {
25     if(ans||sum>k||sum+s[i]<k) return;
26     if(i==n)
27     {
28         if(sum==k)  ans=true;
29         return;
30     }
31     dfs(i+1,sum+a[i]);
32     dfs(i+1,sum);
33 }

View Code

dfs小练 【dfs】

dfs小练【dfs】