hdu 1043 Eight (bfs)

反向bfs + 康托展开

#include<iostream>
#include<string>
#include<queue>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

typedef long long ll;
typedef pair<string, int> pvi;

const int maxn = 10;

int vis[362880+5+5], res; 
string path[362880+5+5];
int tmp[maxn];
int fac[maxn];
int vi[maxn];

string dir = "udlr";

char x; 

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

struct node
{
    string path;
    int hashs;
    int pos;
};
node now, net;

int ktzk(){
	memset(vi, 0, sizeof(vi));
	
	int res = 0;
	for(int i = 0 ; i < 9 ; ++i){
		int cnt = 0;
		for(int j = 1 ; j < tmp[i] ; ++j){
			if(!vi[j]) ++cnt;
		}
		vi[tmp[i]] = 1;
		res += cnt * fac[9 - i - 1];
	}
	return res;
}

void nktzk(int ha){
	vector<int> v;
	for(int i = 1 ; i <= 9 ; ++i) v.push_back(i);
	
	for(int i = 0 ; i < 9 ; ++i){
		int r = ha / fac[9 - i - 1];
		sort(v.begin(),v.end());
		tmp[i] = v[r];
		v.erase(v.begin() + r);
		ha = ha % fac[9 - i - 1];
	}
	
//	for(int i = 0 ; i < 9 ; ++i) printf("%d ", tmp[i]); printf("
"); 
}

void bfs(){
	memset(vis, 0, sizeof(vis));
	queue<node> q;
	for(int i = 0 ; i < 9 ; ++i) tmp[i] = i + 1;
	int ha = ktzk();
//	printf("%d
", ha);

	now.pos = 8;
	now.path = "";
	now.hashs = ha;
	
	q.push(now);
	while(q.size()){
		node u = q.front(); q.pop();
		//printf("%d
", u.second);
		
		if(vis[u.hashs]) continue;
		vis[u.hashs] = 1;
		path[u.hashs] = u.path;
		
		nktzk(u.hashs);
//		for(int i = 0 ;i < 9 ; ++i){
//			printf("%d ", tmp[i]);
//		} printf("
"); 
		
		for(int j = 0 ; j < 4 ; ++j){
			int xx = u.pos / 3 + dx[j], yy = u.pos % 3 + dy[j];
			
			if(xx >= 0 && xx < 3 && yy >= 0 && yy < 3){
				net.pos = xx * 3 + yy;
				net.path = dir[j] + u.path;

				swap(tmp[u.pos], tmp[net.pos]);
				int tha = ktzk();
				
				net.hashs = tha;
				q.push(net);
				swap(tmp[u.pos], tmp[net.pos]);
			}
		}
	} 
} 

ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }

int main(){
	fac[0] = 1;
	for(int i = 1 ; i <= 9 ; ++i) fac[i] = fac[i - 1] * i;
	
	bfs();
	
	while(cin >> x){
		tmp[0] = x == 'x' ? 9 : x - '0';
		
		for(int i = 1 ; i < 9 ; ++i){
			cin >> x;
			tmp[i] = x == 'x' ? 9 : x - '0';
		}
		
		res = ktzk();
		
		if(!vis[res]) cout << "unsolvable" << endl;
		else {
			cout << path[res] << endl;
		}
//		printf("zhixing
");
	}
	return 0;
}