【洛谷P2324】[SCOI2005]骑士精神

骑士精神

题目链接

#include<iostream>

#include<cstdio>

using namespace std;

int t,MAXD,sx,sy;

int a[][];

int dx[]={,-,-,,-,,-,,};

int dy[]={,-,-,-,,-,,,};

inline void read()

{

    char c;

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

    {

        while((c<''||c>'')&&c!='*') c=getchar();

        for(int j=;j<=;j++)

        {

            if(c=='*')

            {

                sx=i;sy=j;

                a[i][j]=;

                c=getchar();

                continue;

            }

            a[i][j]=c-'';

            c=getchar();

        }

    }

}

int aim[][]={{,,,,,},{,,,,,},{,,,,,},{,,,,,},{,,,,,},{,,,,,}};

inline int close()　　　　//估价函数

{

    int Ans=;

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

     for(int j=;j<=;j++)

      Ans+=aim[i][j]^a[i][j];

    return Ans>>;

}

inline bool dfs(int t,int x,int y,int pre)

{

    if(t>) return ;

    int f=close();

    if(f==)

    {

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

        return ;

    }

    if(t+f>MAXD) return ;

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

     if(i+pre!=)

     {

         int xx=x+dx[i],yy=y+dy[i];

        if(<=xx&&xx<=&&<=yy&&yy<=)

        {

            a[x][y]=a[xx][yy];

            a[xx][yy]=;

            if(dfs(t+,xx,yy,i)) return ;

            a[xx][yy]=a[x][y];

            a[x][y]=;

        }

     }

     return ;

}

int main()

{

    scanf("%d",&t);

    while(t--)

    {

        read();

        bool f=;

        for(MAXD=;MAXD<=;MAXD++)　　　　//迭代加深

         if(dfs(,sx,sy,)){

          f=;

          break;

        }

        if(!f)

        puts("-1");

    }

    return ;

}