题目链接：http://acm.hit.edu.cn/hoj/problem/view?id=1868
超时的写法：容易想到的是一遍搜索，把所有的状态都保留下来，我们只要建立0-8的全排列和0-362879的对应起来，就可以了。其中fact数组保留了以当前标号开始的全排列的个数。但是很遗憾，这样是会TLE的。
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;typedef int State[9];
#define Maxn 400000
#define Maxm 362900State st[Maxn],goal;
int dist[Maxn];
int vis[Maxm];
int fact[9];int total = 0;
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};void init_lookup_table()
{fact[0] = 1;for(int i=1;i<9;i++) fact[i] = fact[i-1] * i;
}
int try_to_insert(int s)
{int code = 0;for(int i=0;i<9;i++){int cnt = 0;for(int j=i+1;j<9;j++) if(st[s][j] < st[s][i]) cnt++;code += fact[8-i] * cnt;}if(vis[code]) return 0;return vis[code] = 1;
}
int bfs()
{int front = 1,rear = 2;while(front<rear){State & s = st[front];if(memcmp(goal,s,sizeof(s)) == 0) return front;int z;for(z = 0;z<9;z++) if(!s[z]) break;int x = z/3,y = z%3;for(int d = 0;d<4;d++){int newx = x + dx[d];int newy = y + dy[d];int newz = newx*3 + newy;if(newx>=0 && newx <3 && newy>=0 && newy<3){State &t = st[rear];memcpy(&t,&s,sizeof(s));t[newz] = s[z];t[z] = s[newz];dist[rear] = dist[front] + 1;if(try_to_insert(rear)) rear++;}}front++;total = rear;}return -1;
}
void init()
{memset(vis,0,sizeof(vis));memset(dist,0,sizeof(dist));
}
int main()
{
#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);
#endifint t;int ans;scanf(" %d",&t);init_lookup_table();while(t--){init();for(int i=0; i<9; i++) scanf(" %d",&st[1][i]);for(int i=0;i<9;i++) scanf(" %d",&goal[i]);ans = bfs();if(ans == -1) puts("-1");else printf("%d\n",dist[ans]);}return 0;
}
另一种超时的方法是用哈希来建立映射。
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;typedef int State[9];
#define Maxn 400000
#define Hash_size 1000003State st[Maxn],goal;
int dist[Maxn];int head[Hash_size],next[Maxn];int total = 0;
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};int hash_handle(State &s)
{int v = 0;for(int i=0;i<9;i++) v = v*10 + s[i];return v % Hash_size;
}void init_lookup_table()
{memset(head,0,sizeof(head));
}
int try_to_insert(int s)
{int h = hash_handle(st[s]);int u = head[h];while(u){if(memcmp(st[u],st[s],sizeof(st[s])) == 0) return 0;u = next[u];}next[s] = head[h];head[h] = s;return 1;
}
int bfs()
{int front = 1,rear = 2;while(front<rear){State & s = st[front];if(memcmp(goal,s,sizeof(s)) == 0) return front;int z;for(z = 0;z<9;z++) if(!s[z]) break;int x = z/3,y = z%3;//printf("front = %d,rear = %d\n",front,rear);//printf("x = %d,y = %d\n",x,y);for(int d = 0;d<4;d++){int newx = x + dx[d];int newy = y + dy[d];int newz = newx*3 + newy;if(newx>=0 && newx <3 && newy>=0 && newy<3){State &t = st[rear];memcpy(&t,&s,sizeof(s));t[newz] = s[z];t[z] = s[newz];dist[rear] = dist[front] + 1;if(try_to_insert(rear)) rear++;}}front++;total = rear;}return -1;
}
void init()
{//memset(vis,0,sizeof(vis));memset(dist,0,sizeof(dist));
}
int main()
{
#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);
#endifint t;int ans;scanf(" %d",&t);while(t--){init_lookup_table();init();for(int i=0; i<9; i++) scanf(" %d",&st[1][i]);for(int i=0;i<9;i++) scanf(" %d",&goal[i]);ans = bfs();if(ans == -1) puts("-1");else printf("%d\n",dist[ans]);}return 0;
}
以上两种超时的原因是只有一个方向的搜索，所以我改成了双广BFS+Hash。
但是依然超时，我不知道为什么，求告知。
代码:
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
using namespace std;#define Hash_size 455809
struct State
{int num;int zero;int g;State(){}
};State first,last;struct Hash_node
{State st;Hash_node * next;Hash_node(){next = NULL;}
};Hash_node hash_node[2][Hash_size];int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};int a[9],b[9];queue<State> q1,q2;bool same(State x,State y)
{if(x.num == y.num) return true;return false;
}
int getHash(State s)
{return s.num % Hash_size ;
}
int try_to_insert(State x,int kind)
{int h = getHash(x);Hash_node * u = &hash_node[kind][h];while(u->next!=NULL){if(same(x,u->next->st)) return 0;u = u->next;}u->next = new Hash_node;u->next->st = x;return 1;
}bool exist(State x,int kind)
{int h = getHash(x) ;Hash_node * u= &hash_node[kind][h];while(u->next!=NULL){if(same(x,u->next->st)) return true;u = u->next;}return false;
}int handle(int num,int zero1,int zero2)
{int st[9];for(int i=8;i>=0;i--){st[i] = num%10;num/=10;}int x = st[zero1];st[zero1] = st[zero2];st[zero2] = x;num = 0;for(int i=0;i<=8;i++){num = num*10 + st[i];}return num;
}
int bfs()
{int code;int x,y,newx,newy,z,newz,d;while(!q1.empty()) q1.pop();while(!q2.empty()) q2.pop();q1.push(first);q2.push(last);try_to_insert(first,0);try_to_insert(last,1);while(!q1.empty() || !q2.empty()){int n1 = q1.size();int n2 = q2.size();//处理环Aif(n1 < n2 || n2 == 0){//一层扩展for(int i=0; i<n1; i++){State s = q1.front();q1.pop();//在对方这个状态是否存在if(exist(s,1)) return s.g + q2.front().g;z = s.zero;x = z/3;y = z%3;for(d=0; d<4; d++){newx = x + dx[d];newy = y + dy[d];newz = newx*3 + newy;if(newx>=0 && newx <3 && newy>=0 && newy<3){State t = s;t.num = handle(s.num,z,newz);t.g = s.g + 1;t.zero = newz;if(try_to_insert(t,0)) q1.push(t);}}}}//处理环Belse{//一层扩展for(int i=0; i<n2; i++){State s = q2.front();q2.pop();if(exist(s,0)) return s.g + q1.front().g;z = s.zero;x = z/3;y = z%3;for(d=0; d<4; d++){newx = x + dx[d];newy = y + dy[d];newz = newx*3 + newy;if(newx>=0 && newx <3 && newy>=0 && newy<3){State t = s;t.num = handle(s.num,z,newz);t.g = s.g + 1;t.zero = newz;if(try_to_insert(t,1)) q2.push(t);}}}}}return 0;
}//求逆序数对，要排除第二个数字是0的那种情况
bool reversePair()
{int ansA = 0,ansB = 0;for(int i=0; i<9; i++){for(int j=i+1; j<9; j++){if(a[i]>a[j] && a[j]!=0) ansA++;if(b[i]>b[j] && b[j]!=0) ansB++;}}if((ansA + ansB)%2) return true;return false;
}
bool preJudge()
{if(same(first,last)){puts("0");return false;}else if(reversePair()){puts("-1");return false;}return true;
}
int main()
{
#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);
#endifint t;int ans;int zero;int v;scanf(" %d",&t);while(t--){v = 0;for(int i=0; i<9; i++){scanf(" %d",&a[i]);if(a[i] == 0) zero = i;v = v*10 + a[i];}first.g = 0;first.num = v;first.zero = zero;v = 0;for(int i=0; i<9; i++){scanf(" %d",&b[i]);if(b[i] == 0) zero = i;v = v*10 + b[i];}last.g = 0;last.num = v;last.zero = zero;if(preJudge()){ans = bfs();printf("%d\n",ans);}}return 0;
}
于是，我又写了一发双广BFS+全排列映射。A掉了。
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
using namespace std;#define Maxn 400000
#define Maxm 400000
struct State
{int a[9];int zero;int g;State(){}State(int b[9]){for(int i=0; i<9; i++){a[i]=b[i];if(b[i]==0) zero=i;}g=0;}
};int dist[2][Maxn];
int fact[9];
int vis[2][Maxm];
State first,last;int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};queue<State> q1,q2;void init_lookup_table()
{fact[0] = 1;for(int i=1; i<9; i++) fact[i] = fact[i-1] * i;
}
bool same(State x,State y)
{for(int i=0; i<9; i++){if(x.a[i]!= y.a[i]) return false;}return true;
}
int getcode(State x)
{int code=0;for(int i=0; i<9; i++){int cnt=0;for(int j=i+1; j<9; j++){if(x.a[i]>x.a[j]) cnt++;}code+=fact[8-i]*cnt;}return code;
}
int try_to_insert(State x,int kind)
{int code = getcode(x);if(vis[kind][code]) return 0;dist[kind][code] = x.g;return vis[kind][code] = 1;
}int bfs()
{int code;int x,y,newx,newy,z,newz,d;memset(dist,0,sizeof(dist));memset(vis,0,sizeof(vis));while(!q1.empty()) q1.pop();while(!q2.empty()) q2.pop();q1.push(first);q2.push(last);try_to_insert(first,0);try_to_insert(last,1);while(!q1.empty() || !q2.empty()){int n1 = q1.size();int n2 = q2.size();//处理环Aif(n1 < n2 || n2 == 0){//一层扩展for(int i=0; i<n1; i++){State s = q1.front();q1.pop();code = getcode(s);//在对方这个状态是否存在if(vis[1][code]) return dist[0][code] + dist[1][code];z = s.zero;x = z/3;y = z%3;for(d=0; d<4; d++){newx = x + dx[d];newy = y + dy[d];newz = newx*3 + newy;if(newx>=0 && newx <3 && newy>=0 && newy<3){State t = s;t.a[newz] = s.a[z];t.a[z] = s.a[newz];t.g = s.g + 1;t.zero = newz;if(try_to_insert(t,0)) q1.push(t);}}}}//处理环Belse{//一层扩展for(int i=0; i<n2; i++){State s = q2.front();q2.pop();code = getcode(s);//在对方这个状态是否存在if(vis[0][code]) return dist[0][code] + dist[1][code];z = s.zero;x = z/3;y = z%3;for(d=0; d<4; d++){newx = x + dx[d];newy = y + dy[d];newz = newx*3 + newy;if(newx>=0 && newx <3 && newy>=0 && newy<3){State t = s;t.a[newz] = s.a[z];t.a[z] = s.a[newz];t.g = s.g + 1;t.zero = newz;if(try_to_insert(t,1)) q2.push(t);}}}}}return 0;
}//求逆序数对，要排除第二个数字是0的那种情况
int reversePair(State s)
{int ans = 0;for(int i=0; i<9; i++){for(int j=i+1; j<9; j++) if(s.a[i]>s.a[j] && s.a[j]!=0) ans++;}return ans;
}
bool preJudge()
{if(same(first,last)){puts("0");return false;}else if((reversePair(first) + reversePair(last))%2){puts("-1");return false;}return true;
}
int main()
{
#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);
#endifint t;int ans;int begin[9],end[9];scanf(" %d",&t);init_lookup_table();while(t--){for(int i=0; i<9; i++) scanf(" %d",&begin[i]);State a(begin);first = a;for(int i=0; i<9; i++) scanf(" %d",&end[i]);State b(end);last = b;if(preJudge()){ans = bfs();printf("%d\n",ans);}}return 0;
}
