其实…现在…唯一能满足我的… 就只有用 Astar 把它解出来了。。。
#include
using namespace std;
const int F[9] = {1,1,2,6,24,120,720,5040,40320};
int queue[362880], dist[362880]; bool hash[362880];
int head, tail, goal;
int a[9], b[2]; bool c[9];
int cantor(){
int x = 0, t, i, j;
for (i=0;i<9;i++){
for (j=i+1,t=0;j<9;j++)
if (a[i]>a[j]) t++;
x = x * (9-i) + t;
}
return x;
}
void recover(int x){
memset(c, false, sizeof(c));
memset(a, 0, sizeof(a));
int t, i;
for (i=0;i<9;i++){
while (c[a[i]]) a[i]++;
while (x >= F[8-i]){
x -= F[8-i]; a[i]++;
while (c[a[i]]) a[i]++;
}
c[a[i]] = true;
}
}
int stat(){
int inversion_pair = 0;
for (int i=0;i<8;i++){
if (a[i]==0) continue;
for (int j=i+1;j<9;j++){
if (a[j]==0) continue;
if (a[i]>a[j]) inversion_pair++;
}
}
return inversion_pair;
}
void init(){
int i, j, t;
for (i=0;i<9;i++) cin >> a[i];
queue[0] = cantor(); b[0] = stat();
for (i=0;i<9;i++) cin >> a[i];
goal = cantor(); b[1] = stat();
}
bool operate(int x, int y){
swap(a[x], a[y]); queue[tail] = cantor(); swap(a[x], a[y]);
if (hash[queue[tail]]) return false;
dist[tail] = dist[head] + 1;
if (queue[tail]==goal){
cout << dist[tail] << endl;
return true;
}
hash[queue[tail++]] = true;
return false;
}
void bfs(){
if (queue[0] == goal) {cout << 0 << endl; return;}
if (b[0]%2!=b[1]%2) {cout << -1 << endl; return;}
dist[0] = 0; head = 0; tail = 1;
memset(hash, false, sizeof(hash));
hash[queue[0]] = true;
int p;
while (true){
recover(queue[head]);
for (p=0;a[p]!=0;p++);
if (p > 2) if (operate(p, p-3)) return;
if (p < 6) if (operate(p, p+3)) return;
if (p % 3) if (operate(p, p-1)) return;
if ((p+1) % 3) if (operate(p, p+1)) return;
head ++;
}
}
int main(){
int T; cin >> T;
while (T--){
init(); bfs();
}
}
#include
#define label exitus
using namespace std;
const int F[9] = {1,1,2,6,24,120,720,5040,40320}, FOUND = 3;
int queue[2][362880], dist[2][362880], hash[362880];
int head[2], tail[2], flag;
int a[9], b[2]; bool c[9];
int cantor(){
int x = 0, t, i, j;
for (i=0;i<9;i++){
for (j=i+1,t=0;j<9;j++)
if (a[i]>a[j]) t++;
x = x * (9-i) + t;
}
return x;
}
void recover(int x){
memset(c, false, sizeof(c));
memset(a, 0, sizeof(a));
int i;
for (i=0;i<9;i++){
while (c[a[i]]) a[i]++;
while (x >= F[8-i]){
x -= F[8-i]; a[i]++;
while (c[a[i]]) a[i]++;
}
c[a[i]] = true;
}
}
int stat(){
int inversion_pair = 0;
for (int i=0;i<8;i++){
if (a[i]==0) continue;
for (int j=i+1;j<9;j++){
if (a[j]==0) continue;
if (a[i]>a[j]) inversion_pair++;
}
}
return inversion_pair;
}
void init(){
int i;
for (i=0;i<9;i++) cin >> a[i];
queue[0][0] = cantor(); b[0] = stat();
for (i=0;i<9;i++) cin >> a[i];
queue[1][0] = cantor(); b[1] = stat();
}
inline void operate(int x, int y){
swap(a[x], a[y]); queue[flag][tail[flag]] = cantor(); swap(a[x], a[y]);
if (hash[queue[flag][tail[flag]]]==flag) return ;
dist[flag][tail[flag]] = dist[flag][head[flag]] + 1;
if (hash[queue[flag][tail[flag]]]== 1 - flag){
int pos;
for (pos=head[1-flag];queue[1-flag][pos]!=queue[flag][tail[flag]];pos++);
cout << dist[flag][tail[flag]] + dist[1 - flag][pos] << endl;
flag = FOUND;
return;
}
hash[queue[flag][tail[flag]++]] = flag;
return ;
}
inline void expand(){
int p; recover(queue[flag][head[flag]]);
for (p=0;a[p]!=0;p++);
if (p > 2) {operate(p, p-3); if (flag == FOUND) return;}
if (p < 6) {operate(p, p+3); if (flag == FOUND) return;}
if (p % 3) {operate(p, p-1); if (flag == FOUND) return;}
if ((p+1) % 3) {operate(p, p+1); if (flag == FOUND) return;}
head[flag]++;
}
void bibfs(){
if (queue[0][0] == queue[1][0]) {cout << 0 << endl; return;}
if (b[0]%2!=b[1]%2) {cout << -1 << endl; return;}
dist[0][0] = dist[1][0] = 0; head[0] = head[1] = 0; tail[0] = tail[1] = 1;
memset(hash, -1, sizeof(hash)); hash[queue[0][0]] = 0; hash[queue[1][0]] = 1;
while (true){
//if (head[0]> T;
while (T--){
init(); bibfs();
}
}
#include
#include
#define REP(I, N) for (int I=0;I x.f;
}
} u, v;
priority_queue Q;
/*/
inline int h(){
int s = 0; REP(i, 9) if (a[i] && a[i] != ed[i]) s++;
return s;
}
/*/
inline int h(){
int s = 0; REP(i, 9) s += w[i][a[i]];
return s + s / 5; //#
}
//*/
inline int cantor(){
int x = 0, t, i, j;
for (i=0;i<9;i++){
for (j=i+1,t=0;j<9;j++)
if (a[i]>a[j]) t++;
x = x * (9-i) + t;
}
return x;
}
inline void recover(int x){
memset(c, false, sizeof(c));
memset(a, 0, sizeof(a));
int i;
for (i=0;i<9;i++){
while (c[a[i]]) a[i]++;
while (x >= F[8-i]){
x -= F[8-i]; a[i]++;
while (c[a[i]]) a[i]++;
}
c[a[i]] = true;
}
}
inline int stat(){
int inversion_pair = 0;
for (int i=0;i<8;i++){
if (a[i]==0) continue;
for (int j=i+1;j<9;j++){
if (a[j]==0) continue;
if (a[i]>a[j]) inversion_pair++;
}
}
return inversion_pair;
}
void init(){
REP(i, 9){cin >> st[i]; a[i] = st[i];}
start = cantor(); b[0] = stat();
REP(i, 9){cin >> ed[i]; a[i] = ed[i];}
goal = cantor(); b[1] = stat();
REP(i, 9) st[ed[i]] = i; // #
REP(i, 9) REP_1(j, 8) w[i][j] = abs(i/3 - st[j]/3) + abs(i%3 - st[j]%3);
_found = false;
}
inline void operate(int x, int y){
swap(a[x], a[y]), v.s = cantor();
if (!hash[v.s]){
v.d = u.d + 1;
if (v.s==goal){
cout << v.d << endl;
_found = true;
}
else {
v.f = v.d + h();
Q.push(v);
}
}
swap(a[x], a[y]);
}
void Astar(){
if (start == goal) {cout << 0 << endl; return;}
if (b[0]%2!=b[1]%2) {cout << -1 << endl; return;}
while (!Q.empty()) Q.pop(); //#
u.s = start, u.d = 0, Q.push(u);
memset(hash, false, sizeof(hash));
int p;
while (true){
u = Q.top(); Q.pop(); if (hash[u.s]==true) continue;
hash[u.s] = true; recover(u.s);
for (p=0;a[p]!=0;p++);
if (p > 2) operate(p, p-3);
if (p < 6) operate(p, p+3);
if (p % 3) operate(p, p-1);
if ((p+1) % 3) operate(p, p+1);
if (_found) return;
}
}
int main(){
int T; cin >> T;
while (T--){
init(); Astar();
}
}
http://acm.hit.edu.cn/judge/show.php?Proid=1868&Contestid=0
1. 状态的存储
状态的存储采用康托展开对排列进行编码起到 hash 的作用，唯一的缺点呢则是在应用操作符的时侯需要解码恢复一次。
（参见代码中的 void cantor() 和 void recover() 过程。。。。。）
2. 判断无解
另一个重要的想法是利用逆序对的奇偶性将状态划分成两个等价类，不同等价类的里状态不能相互达到，这样在宽搜之前就可以排除掉输出-1的情况。
3. 关于 Astar
目前关于 Astar 还存在一些疑问有待解决 …
在这题里而言，首先同普通 BFS 的一个显著不同，虽然边权值都只有＋1而已，但是只能保证在取出队列的时侯所得到的值最优，（这点又类似 Dijkstra 了）因此理因，在每次更新状态的时侯先要判断这个状态在优先队列中是否已经存在，如果存在则进行比较并更新。（但是这一份代码并没有这么做，而是让两个状态同时加入到结点中，而在取出队列的时侯对状态进行标记，这样会有一些不好的地方，但是这是在用 STL 写的时侯无法获得 堆中元素的 Pos 数组而采取的一种替代方式。）
另外，关于 八数码问题 的两种启发函数，（每个元素到自己理应所在点的哈密顿距离，以及所有不在自己位置上的数。）（注意不能考虑数字 0 ，具体原因。。。）也有一些值得讨论的地方呢。
