[修改模板] 主题列表页 发帖图标旁 加 【本版搜索】代码 [复制链接]

兰博基尼

回复 1# oocn


    #include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int T,ans=20,flag;
int xx[9]={0,-2,-2,-1,-1,1,1,2,2};
int yy[9]={0,-1,1,-2,2,2,-2,1,-1};
int s[10][7],get[10][10];
int map[10][10];
char si;
int Judge()
{
    int ret=0;
    for(int i=1;i<=5;i++)
    {
        for(int j=1;j<=5;j++)
        {
            if(s[j]!=map[j])
            {
                ret++;
            }
        }
    }
    return ret;
}
void dfs(int now,int x,int y,int sum)
{
    if(flag!=0)
    {
        return;
    }
    int c=Judge();
    if(now==sum)
    {
        if(c==0)
        {
            flag=1;
            ans=sum;
        }
    }
    if(now-1+c>sum)
    {
        return;
    }
    for(int i=1;i<=8;i++)
    {
        int nx=x+xx;
        int ny=y+yy;
        if(nx>0 && nx<=5 && ny>0 && ny<=5)
        {
            swap(s[x][y],s[nx][ny]);
            dfs(now+1,nx,ny,sum);
            swap(s[x][y],s[nx][ny]);
        }
    }
}
int main()
{
    scanf("%d",&T);
    map[1][1]=1;
    map[1][2]=1;
    map[1][3]=1;
    map[1][4]=1;
    map[1][5]=1;
    map[2][1]=0;
    map[2][2]=1;
    map[2][3]=1;
    map[2][4]=1;
    map[2][5]=1;
    map[3][1]=0;
    map[3][2]=0;
    map[3][3]=2;
    map[3][4]=1;
    map[3][5]=1;
    map[4][1]=0;
    map[4][2]=0;
    map[4][3]=0;
    map[4][4]=0;
    map[4][5]=1;
    map[5][1]=0;
    map[5][2]=0;
    map[5][3]=0;
    map[5][4]=0;
    map[5][5]=0;
    while(T--)
    {
        int x,y;
        for(int i=1;i<=5;i++)
        {
            for(int j=1;j<=5;j++)
            {
                cin>>si;
                if(si=='*')
                {
                    x=i;
                    y=j;
                    get[j]=2;
                }   
                else
                {
                    get[j]=si-'0';
                }
            }
        }
        for(int k=0;k<=20;k++)
        {
            flag=0;
            ans=20;
            for(int i=1;i<=5;i++)
            {
                for(int j=1;j<=5;j++)
                {
                    s[j]=get[j];
                }
            }
            dfs(0,x,y,k);
            if(ans==k)
            {
                break;
            }
        }
        if(ans<=15)
        {
            printf("%d\n",ans);
        }
        else
        {
            printf("-1\n");
        }
    }
    return 0;
}