这题很经典也很简单就不放思路了QAQ
留个代码防我健忘
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
#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; } |