bzoj1085

题解：

暴搜+优化

如果当前有n个位置不符合，那么至少要n-1次才可以

然后就可以优化了

代码：

#include<bits/stdc++.h>
#define y1 ____y1
using namespace std;
int dx[8]={1,-1,1,-1,2,2,-2,-2};
int dy[8]={2,2,-2,-2,1,-1,1,-1};
int f[7][7],a[7][7],ans,T,x,y;
char s[7];
void dfs(int p,int x,int y)
{
    int ss=0;
    for (int i=1;i<=5;i++)
     for (int j=1;j<=5;j++)
      if (f[i][j]!=a[i][j])ss++;    
    if (!ss)
     {
         if (p<ans)ans=p;
         return;
     }
    if (p+ss>ans)return;
    for (int i=0;i<8;i++)
     {
         int x1=x+dx[i],y1=y+dy[i];
         if (x1>0&&x1<6&&y1>0&&y1<6)
          {
              swap(a[x1][y1],a[x][y]);
              dfs(p+1,x1,y1);
              swap(a[x1][y1],a[x][y]);
         }
     }
}
void init()
{
    for (int i=1;i<=5;i++)
     for (int j=i;j<=5;j++)f[i][j]=1;
    f[3][3]=-1;f[4][4]=f[5][5]=0; 
}
int main()
{
    scanf("%d",&T);
    init();
    while (T--)
     {
         for (int i=1;i<=5;i++)
          {
              scanf("%s",s+1);
              for (int j=1;j<=5;j++)
               if (s[j]=='*')
                {
                   x=i;y=j;
                a[i][j]=-1;    
              }
             else a[i][j]=s[j]-'0'; 
         }
        ans=16;
         dfs(0,x,y);
        if (ans==16)puts("-1");
        else printf("%d
",ans); 
     }
}