C++14(g++5.4) 解法, 执行用时: 319ms, 内存消耗: 8036K, 提交时间: 2019-09-30 17:19:25

#include <bits/stdc++.h>
using namespace std;
int fac[]={1,1,2,6,24,120,720,5040,40320,362880};
int ans[370000];
string mp[]={"672159834","834159672","294753618","492357816","816357492","618753294","438951276","276951438"};
int gethash(string s){
    int ans=0;
    for(int i=0;i<8;i++){
        int cnt=0;
        for(int j=i+1;j<9;j++){
            if(s[j]<s[i])cnt++;
        }
        ans+=fac[8-i]*cnt;
    }
    return ans;
}
struct node{string s;int step;node(string s,int step):s(s),step(step){}};
queue<node>q;
int dir[12][2]={{0,1},{1,2},{3,4},{4,5},{6,7},{7,8},
                {0,3},{3,6},{1,4},{4,7},{2,5},{5,8}};

void bfs(){
    for(int i=0;i<8;i++){ans[gethash(mp[i])]=0;q.push(node(mp[i],0));}
    while(!q.empty()){
        node now=q.front();q.pop();
        //if(ans[gethash(now.s)]<now.step)continue;
        for(int i=0;i<12;i++){
            swap(now.s[dir[i][0]],now.s[dir[i][1]]);
            int id=gethash(now.s);
            if(ans[id]>now.step+1){ans[id]=now.step+1;q.push(node(now.s,now.step+1));}
            swap(now.s[dir[i][0]],now.s[dir[i][1]]);
        }
    }
}
string s;
int main(){
    int T,a;
    scanf("%d",&T);
    for(int i=0;i<fac[9];i++)ans[i]=0x3f3f3f3f;
    //for(int i=0;i<8;i++)
    bfs();
    //for(int i=0;i<8;i++)cout<<ans[gethash(mp[i])]<<endl;
    while(T--){
        s.clear();
        for(int i=0;i<9;i++)scanf("%d",&a),s+=char(a+'0');
        //cout<<s<<endl;
        printf("%d\n",ans[gethash(s)]);
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 256ms, 内存消耗: 6756K, 提交时间: 2019-01-26 16:54:48

#include<bits/stdc++.h>
using namespace std;
const int fac[]={1,1,2,6,24,120,720,5040,40320,362880};
const string final[]={"672159834","834159672","294753618","492357816","816357492","618753294","438951276","276951438"};
int ans[370000];

int gethash(string st) {
	int res=0;
	for (int i=0;i<8;i++) {
		int cnt=0;
		for (int j=i+1;j<9;j++) if (st[i]>st[j]) cnt++;
		res+=cnt*fac[8-i];
	}
	return res;
}

queue<string> q;
const int dir[12][2]={{0,1},{1,2},{3,4},{4,5},{6,7},{7,8},{0,3},{3,6},{1,4},{4,7},{2,5},{5,8}};
void bfs() {
	memset(ans,0x3f,sizeof(ans));
	for (int i=0;i<8;i++) {
		ans[gethash(final[i])]=0;
		q.push(final[i]);
	}
	while (!q.empty()) {
		string now=q.front(); q.pop();
		int nowh=gethash(now);
		for (int i=0;i<12;i++) {
			swap(now[dir[i][0]],now[dir[i][1]]);
			int h=gethash(now);
			if (ans[h]>ans[nowh]+1) {
				ans[h]=ans[nowh]+1;
				q.push(now);
			}
			swap(now[dir[i][0]],now[dir[i][1]]);
		}
	}
}

int main()
{
	int T; scanf("%d",&T);
	bfs();
	string s;
	while (T--) {
		s.clear();
		for (int i=1;i<=9;i++) {
			int x; scanf("%d",&x);
			s+=(char)(x+'0');
		}
		printf("%d\n",ans[gethash(s)]);
	}
	return 0;
}