学步园

题目链接~~>

                这题其实很简单，开始做题时很盲目，上来就用广搜（可能是广搜用习惯的缘故），果断超时，后来仔细想了一下，很明显用深搜嘛 ！深搜写了一下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 ;
}