八数码问题 经典搜索 bfs
/*这道题a的蛋疼无比啊。学了hash技术和cantor展开。具体的解释都在注释下。不多说了。好题啊！*/#include<cstdio>#include<set>#include <cstring>using namespace std;typedef int State[9];const int MAXSTATE = 1000000;State st[MAXSTATE], goal;int dist[MAXSTATE];const int MAXHASHSIZE = 1000003;int head[MAXHASHSIZE], next[MAXSTATE];void init_lookup_table() { memset(head, 0, sizeof(head)); }int hash(State& s) { int v = 0; for(int i = 0; i < 9; i++) v = v * 10 + s[i]; return v % MAXHASHSIZE;}int try_to_insert(int s) { int h = hash(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;}const int dx[] = {-1, 1, 0, 0};const int dy[] = {0, 0, -1, 1};int bfs() { init_lookup_table(); 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++; } return 0;}int main() { int t; scanf("%d",&t); while(t--) { getchar(); for(int i=0; i<9; i++) scanf("%d",&st[1][i]); for(int i=0; i<9; i++) scanf("%d",&goal[i]); int ans=bfs(); if(ans==0) printf("-1\n"); else printf("%d\n",dist[ans]); } return 0;}