dfs小练【dfs】-白红宇

dfs小练【dfs】

阅读量：5374 次

发布时间：2019-06-15

本文共 2604 字，大约阅读时间需要 8 分钟。

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

1 #include 
      
        2 #include 
       
         3 #include 
        
          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 
      
        2 #include 
       
         3 #include 
        
          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 
      
        2 #include 
       
         3 #include 
        
          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
         
          =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]