题目

 

 

分析

我好菜啊。

一波IDA*水过去了。

 

代码

#include 
      
       using namespace std;const int maxn = 7;char s[maxn][maxn];int a[maxn][maxn], res=0;;int dx[10]={
    1,-1,-1,1,2,-2,-2,2}, dy[10]={
    2,2,-2,-2,1,1,-1,-1};int ans[maxn][maxn]={    {
     0,0,0,0,0,0},    {
     0,1,1,1,1,1},    {
     0,0,1,1,1,1},    {
     0,0,0,2,1,1},    {
     0,0,0,0,0,1},    {
     0,0,0,0,0,0}};int in(int x,int y) { return x>=1&&y>=1&&x<=5&&y<=5; }int check() {    for(int i=1;i<=5;i++)        for(int j=1;j<=5;j++)            if(a[i][j]!=ans[i][j]) return 0;    return 1;}int g() {    int tot=0;    for(int i=1;i<=5;i++)        for(int j=1;j<=5;j++)            if(a[i][j]!=ans[i][j]) tot++;    return tot;}void Astar(int x,int y,int depth,int limit) {    if(depth==limit) {        if(check()) res=limit;        return;    }    for(int i=0;i<8;i++) {        int px=x+dx[i], py=y+dy[i];        if(!in(px,py)) continue;        swap(a[px][py], a[x][y]);        if(g()+depth <= limit) Astar(px,py,depth+1,limit);        swap(a[px][py], a[x][y]);    }}int main() {    int sx,sy,t;    scanf("%d",&t);    while(t--) {        res=0;        for(int i=1;i<=5;i++)            scanf("%s",s[i]+1);        for(int ii=0;ii<=15;ii++) {            for(int i=1;i<=5;i++)                for(int j=1;j<=5;j++) {                    if(s[i][j]=='1') a[i][j]=1;                    else if(s[i][j]=='0') a[i][j]=0;                    else {                        sx=i; sy=j; a[i][j]=2;                    }                }            Astar(sx,sy,0,ii);            if(res) break;        }        if(!res) res--;        printf("%d\n",res);    }    return 0;}