这题很经典也很简单就不放思路了QAQ

留个代码防我健忘

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstdlib>
#include<iterator>
using namespace std;
 
int mapx[6][6]={0},x_pos,y_pos;
int wayx[8]={-1,-2,-2,-1,1,2,2,1},wayy[8]={-2,-1,1,2,-2,-1,1,2},stdmap[6][6]={0},kt,ans=0,mut;
char ch=0;
 
inline void readx(int& x)
{
    x=0; int k=1; register char ch=0;
    while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    x*=k;
}
 
inline int judgex()
{
    int hor=0;
    for (int i=1;i<=5;i++)
        for (int j=1;j<=5;j++)
            if (stdmap[i][j]!=mapx[i][j]) hor++;
    return hor;
}
 
inline void dfs(int xp,int yp,int steps,int pre)
{
    int qs1=judgex(); if (ans!=-1 || qs1+steps-1>mut) return;
    if (!qs1)
    {
        ans=steps;
        return;
    }
    for (int w=0;w<8;w++) if (pre+w!=7)
    {
        if (xp+wayx[w]>0 && xp+wayx[w]<6 && yp+wayy[w]>0 && yp+wayy[w]<6)
        {
            swap(mapx[xp][yp],mapx[xp+wayx[w]][yp+wayy[w]]);
            dfs(xp+wayx[w],yp+wayy[w],steps+1,w);
            swap(mapx[xp][yp],mapx[xp+wayx[w]][yp+wayy[w]]);
        }
    }
}
 
int main()
{
    for (int i=3;i<=5;i++)
        for (int j=1;j<=i;j++) stdmap[i][j]=1;
    for (int i=1;i<=3;i++)
        for (int j=i;j<=5;j++) stdmap[i][j]=2;
    stdmap[3][3]=0; stdmap[2][1]=1; stdmap[4][5]=2;
     
    readx(kt);
    while (kt--)
    {
        for (int i=1;i<=5;i++)
            for (int j=1;j<=5;j++)
            {
                ch=0; while ((ch<'0' || ch>'9') && ch!='*') ch=getchar();
                if (ch=='*') { x_pos=i; y_pos=j; mapx[i][j]=0; }
                else mapx[i][j]=ch-'0'+1; //white->1 black->2
            }
         
        for (int i=0;i<=15;i++)
        {
            ans=-1; mut=i;
            dfs(x_pos,y_pos,0,-11);
            if (ans!=-1) { printf("%d\n",ans); break; }
        }
        if (ans==-1) printf("-1\n");
    }
    return 0;
}

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.