然而并不会做。
最后就照着题解码了一遍/kk
真的好长啊。看时间就知道写了多久...
#include<bits/stdc++.h> using namespace std; typedef long long ll; int cg[9] = {1,2,6,24,120,720,5040,40320}; char s[15]; int n,step,mark[380001]; ll v; struct node{ ll a; int s; }p[400001],now,ad; ll find(ll v) { int ss[15]; for(int i = 9;i >= 1;i --) { ss[i] = v % 10; v /= 10; } ll ret = 0; for(int i = 1;i <= 8;i ++) { int x = 0; for(int j = i + 1;j <= 9;j ++) if(ss[i] > ss[j]) x ++; ret += x * cg[8 - i]; } return ret; } ll chg1(ll x) { ll tmp[10]; for(int i = 9;i >= 1;i --) { tmp[i] = x % 10; x /= 10; } ll t = tmp[1]; tmp[1] = tmp[4]; tmp[4] = tmp[5]; tmp[5] = tmp[2]; tmp[2] = t;x = 0; for(int i=1; i<=9; i ++) { x *= 10; x += tmp[i]; } return x; } ll chg2(ll x) { ll tmp[10]; for(int i = 9;i >= 1;i --) { tmp[i] = x % 10; x /= 10; } ll t = tmp[1]; tmp[1] = tmp[2];tmp[2] = tmp[5];tmp[5] = tmp[4];tmp[4] = t;x = 0; for(int i = 1;i <= 9;i ++) { x *= 10; x += tmp[i]; } return x; } ll chg3(ll x) { ll tmp[10]; for(int i = 9;i >= 1;i --) { tmp[i] = x % 10; x /= 10; } ll t = tmp[2];tmp[2] = tmp[5];tmp[5] = tmp[6];tmp[6] = tmp[3];tmp[3] = t; x=0; for(int i = 1;i <= 9;i ++) { x *= 10; x += tmp[i]; } return x; } ll chg4(ll x) { ll tmp[10]; for(int i = 9;i >= 1;i --) { tmp[i] = x % 10; x /= 10; } ll t = tmp[2]; tmp[2] = tmp[3];tmp[3] = tmp[6]; tmp[6] = tmp[5]; tmp[5] = t; x = 0; for(int i = 1;i <= 9;i ++) { x *= 10; x += tmp[i]; } return x; } ll chg5(ll x) { ll tmp[10]; for(int i = 9;i >= 1;i--) { tmp[i] = x % 10;x /= 10; } ll t = tmp[4];tmp[4]=tmp[7];tmp[7]=tmp[8];tmp[8]=tmp[5];tmp[5]=t;x=0; for(int i = 1;i <= 9;i ++) { x *= 10; x += tmp[i]; } return x; } ll chg6(ll x) { ll tmp[10]; for(int i = 9;i >= 1;i --) { tmp[i] = x % 10; x /= 10; } ll t = tmp[4];tmp[4] = tmp[5];tmp[5] = tmp[8];tmp[8] = tmp[7];tmp[7] = t;x = 0; for(int i = 1;i <= 9;i ++) { x *= 10; x += tmp[i]; } return x; } ll chg7(ll x) { ll tmp[10]; for(int i = 9;i >= 1;i --) { tmp[i] = x % 10; x /= 10; } ll t = tmp[5]; tmp[5] = tmp[8];tmp[8] = tmp[9];tmp[9] = tmp[6];tmp[6] = t;x = 0; for(int i = 1;i <= 9;i ++) { x*=10; x+=tmp[i]; } return x; } ll chg8(ll x) { ll tmp[10]; for(int i = 9; i >= 1; i--) { tmp[i] = x % 10; x /= 10; } ll t = tmp[5]; tmp[5] = tmp[6]; tmp[6] = tmp[9]; tmp[9] = tmp[8]; tmp[8] = t;x = 0; for(int i = 1; i <= 9; i ++) { x *= 10; x += tmp[i]; } return x; } int bfs() { int st = 0,ed = 0; p[ed].a = v, p[ed].s = 0; ed ++; mark[find(v)] = 1; while(st<ed) { now = p[st ++]; if(now.a == 123456789LL) return now.s; if(now.s>step) return -1; ll w; w = chg1(now.a); int ww = find(w); if(mark[ww] == 0) { ad.a = w; ad.s = now.s+1; p[ed ++] = ad; mark[ww] = 1; } w = chg2(now.a); ww = find(w); if(mark[ww] == 0) { ad.a = w; ad.s = now.s+1; p[ed ++] = ad; mark[ww] = 1; } w = chg3(now.a); ww = find(w); if(mark[ww] == 0) { ad.a = w; ad.s = now.s+1; p[ed ++] = ad; mark[ww] = 1; } w = chg4(now.a); ww = find(w); if(mark[ww] == 0) { ad.a = w; ad.s = now.s+1; p[ed ++] = ad; mark[ww] = 1; } w = chg5(now.a); ww = find(w); if(mark[ww] == 0) { ad.a = w; ad.s = now.s+1; p[ed ++] = ad; mark[ww] = 1; } w = chg6(now.a); ww = find(w); if(mark[ww] == 0) { ad.a = w; ad.s = now.s+1; p[ed ++] = ad; mark[ww] = 1; } w = chg7(now.a); ww = find(w); if(mark[ww] == 0) { ad.a = w; ad.s = now.s+1; p[ed ++] = ad; mark[ww] = 1; } w = chg8(now.a); ww = find(w); if(mark[ww] == 0) { ad.a = w; ad.s = now.s+1; p[ed ++] = ad; mark[ww] = 1; } } return -1; } int main() { scanf("%d",&n); while(n--) { memset(mark,0,sizeof(mark)); scanf("%s",s); step = s[0]-'0'; v = 0LL; for(int i = 1; i <= 9; i ++) { v *= 10; v += s[i]-'0'; } int res = bfs(); printf("%d ",res); } return 0; }