HDU_2234
这个题目可以先从终态出发，把5步以内的所有状态预处理出来，同时为了进一步减少状态，利用最小表示法的思想，将终态看成只有两种：
1111
2222
3333
4444
和
1234
1234
1234
1234
，这样我的程序最终跑出来就只有157370个状态了。
在查询的时候，由于前面我们用最小表示法将状态简化了，那么现在就要将1、2、3、4全排列一下生成24种状态，每种状态都查找一下，然后取这24种状态下的最小值。
#include<stdio.h> #include<string.h> #include<algorithm> #define HASH 1000007 #define MAXD 1000010 #define INF 0x3f3f3f3f typedef unsigned int _int; struct HashMap { int head[HASH], size, next[MAXD]; _int st[MAXD]; void init() { memset(head, -1, sizeof(head)); size = 0; } int find(_int _st) { int i, h = _st % HASH; for(i = head[h]; i != -1; i = next[i]) if(st[i] == _st) break; return i; } void push(_int _st) { int h = _st % HASH; st[size] = _st; next[size] = head[h], head[h] = size ++; } }hm; int trans[][4] = { {0, 1, 2, 3}, {0, 1, 3, 2}, {0, 2, 1, 3}, {0, 2, 3, 1}, {0, 3, 1, 2}, {0, 3, 2, 1}, {1, 0, 2, 3}, {1, 2, 0, 3}, {1, 2, 3, 0}, {1, 0, 3, 2}, {1, 3, 0, 2}, {1, 3, 2, 0}, {2, 0, 1, 3}, {2, 0, 3, 1}, {2, 1, 0, 3}, {2, 1, 3, 0}, {2, 3, 0, 1}, {2, 3, 1, 0}, {3, 0, 1, 2}, {3, 0, 2, 1}, {3, 1, 0, 2}, {3, 1, 2, 0}, {3, 2, 0, 1}, {3, 2, 1, 0}, }; _int q[MAXD]; int dis[MAXD], code[4][4]; _int encode(int code[][4]) { int i, j; _int ans = 0; for(i = 0; i < 4; i ++) for(j = 0; j < 4; j ++) ans = ans << 2 | code[i][j]; return ans; } void decode(_int st) { int i, j; for(i = 3; i >= 0; i --) for(j = 3; j >= 0; j --) code[i][j] = st & 3, st >>= 2; } void shr(int r, int k) { int i; if(k == 0) for(i = 0; i < 3; i ++) std::swap(code[r][i], code[r][i + 1]); else for(i = 3; i >= 1; i --) std::swap(code[r][i], code[r][i - 1]); } void shc(int c, int k) { int i; if(k == 0) for(i = 0; i < 3; i ++) std::swap(code[i][c], code[i + 1][c]); else for(i = 3; i >= 1; i --) std::swap(code[i][c], code[i - 1][c]); } void prepare() { int i, j, k, rear = 0; _int x, y; hm.init(); for(i = 0; i < 4; i ++) for(j = 0; j < 4; j ++) code[i][j] = i; x = encode(code); hm.push(x), q[rear ++] = x; for(i = 0; i < 4; i ++) for(j = 0; j < 4; j ++) code[i][j] = j; x = encode(code); hm.push(x), dis[rear] = 0, q[rear ++] = x; for(i = 0; i < rear; i ++) { if(dis[i] >= 5) continue; x = q[i]; decode(x); for(j = 0; j < 4; j ++) for(k = 0; k < 2; k ++) { shr(j, k); y = encode(code); if(hm.find(y) == -1) hm.push(y), dis[rear] = dis[i] + 1, q[rear ++] = y; shr(j, k ^ 1); shc(j, k); y = encode(code); if(hm.find(y) == -1) hm.push(y), dis[rear] = dis[i] + 1, q[rear ++] = y; shc(j, k ^ 1); } } //printf(">> %d\n", rear); } void solve() { int i, j, k, g[4][4], ans = INF; for(i = 0; i < 4; i ++) for(j = 0; j < 4; j ++) scanf("%d", &g[i][j]), -- g[i][j]; for(k = 0; k < 24; k ++) { for(i = 0; i < 4; i ++) for(j = 0; j < 4; j ++) code[i][j] = trans[k][g[i][j]]; i = hm.find(encode(code)); if(i != -1) ans = std::min(ans, dis[i]); } if(ans == INF) printf("-1\n"); else printf("%d\n", ans); } int main() { prepare(); int t; scanf("%d", &t); while(t --) solve(); return 0; }