4月12日-白红宇

4月12日

阅读量：5085 次

发布时间：2019-06-13

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

我做过的dfs大致分为两种:(1)回溯(2)图上几个方向进行搜索

hdu1016(打表＋dfs）（回溯)

题意:一个环里面有m个数，要求两两相加的和为质数，打印出所有排列方案

分析:这题需要用打表+dfs，40以内的素数先求出，然后在直接dfs回溯

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
              9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 #include 
                 
                  13 using namespace std;14 const int maxn=22;15 int a[maxn],vis[maxn];16 int prime[]={ 3,5,7,11,13,17,19,23,29,31,37}; //40以内的素数打表17 int n;18 bool judge(int k)19 {20 int flag=0;21 for(int i=0;i<11;i++)22 {23 if(k==prime[i])24 {25 flag=1; break;26 }27 }28 if(flag) return true;29 else return false;30 }31 void dfs(int step)32 {33 if(step==n&&judge(a[step-1]+a[0]))34 {35 for(int i=0;i
                  
                   >n)56 {57 memset(vis,0,sizeof(vis));58 printf("Case %d:\n",++cas);59 a[0]=1;60 vis[1]=1;61 dfs(1);62 cout<

View Code

hdu1312(图上几个方向进行搜索)

题意:从某个位置开始，统计走过的非＃并且相连的有多少

分析:水题

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
              9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 #include 
                 
                  13 using namespace std;14 const int maxn=30;15 char s[maxn][maxn];16 int n,m;17 int cnt;18 int dx[]={-1,1,0,0},dy[]={ 0,0,-1,1};19 void dfs(int x,int y)20 {21 int nx,ny;22 if(x>n||x<0||y>m||y<0) return;23 s[x][y]='#';24 for(int i=0;i<4;i++)25 {26 nx=x+dx[i],ny=y+dy[i];27 if(nx>=0&&nx
                  
                   =0&&ny
                   
                    >m>>n)37 {38 if(n+m==0) break;39 for(int i=0;i
                    
                     >s[i];41 cnt=0;42 int sx,sy;43 for(int i=0;i