HDU 1584 蜘蛛牌

题目链接~~>

                这题其实很简单，开始做题时很盲目，上来就用广搜（可能是广搜用习惯的缘故），果断超时，后来仔细想了一下，很明显用深搜嘛 ！深搜写了一下wa，找了好久才找出来原来是少标记了一个。。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      int x[12],y[12] ;
     
    
   

    

     

    
    

     

      int min ;
     
    
   

    

     

    
    

     

      int search()//判断是否结束
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 for(int i=0;i<10;i++)
     
    
   

    

     

    
    

     
 if(x[i]==10&&y[i]==1)
     
    
   

    

     

    
    

     
 return 1 ;
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void dfs(int bu)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int i,j,t1,t2,t3  ;
     
    
   

    

     

    
    

     
 if(search())
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(bu<min)//不断与最优值比较
     
    
   

    

     

    
    

     

       min=bu ;
     
    
   

    

     

    
    

     
 return  ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 for(i=0;i<10;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(x[i]!=10&&x[i]!=-5)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 for(j=0;j<10;j++)
     
    
   

    

     

    
    

     
 if(x[i]+1==y[j])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       t1=y[j] ;
     
    
   

    

     

    
    

     

       y[j]=y[i] ;
     
    
   

    

     

    
    

     

       t2=x[i] ;
     
    
   

    

     

    
    

     

       x[i]=-5 ;
     
    
   

    

     

    
    

     

       t3=y[i] ;
     
    
   

    

     

    
    

     

       y[i]=-5 ;
     
    
   

    

     

    
    

     
 if(bu+abs(i-j)<min)//剪枝当大于最优解时没有继续向下搜索的必要。
     
    
   

    

     

    
    

     

       dfs(bu+abs(i-j)) ;
     
    
   

    

     

    
    

     

       y[j]=t1 ;
     
    
   

    

     

    
    

     

       x[i]=t2 ;
     
    
   

    

     

    
    

     

       y[i]=t3 ;
     
    
   

    

     

    
    

     
 break ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int T ;
     
    
   

    

     

    
    

     
 scanf("%d",&T) ;
     
    
   

    

     

    
    

     
 while(T--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 for(int i=0;i<10;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d",&x[i]) ;
     
    
   

    

     

    
    

     

       y[i]=x[i] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       min=9999999 ;
     
    
   

    

     

    
    

     

       dfs(0) ;
     
    
   

    

     

    
    

     
 printf("%d\n",min) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/12418105