题意： 起初定28张卡牌的排列，把其中11, 21, 31, 41移动到第一列，然后就出现四个空白，每个空白可以用它的前面一个数的下一个数填充，例如43后面的空格可以用44填充，但是47后面即使有空白也无法填充，因为没有48。
思路：每次有四个空格，面临四个选择，直接用bfs搜索，状态保存的话就自己设计一个哈希函数，如果找不到完美哈希一定要解决冲突。
我设计的哈希函数：我用的是双哈希，第一个哈希值用于查找，第二个哈希值可以看做整个卡牌状态的压缩，如果有两种状态有同一个第一哈希，我就用第二哈希来判断它们是否一致（第二哈希也一样的可能性几乎没有）。我的时间是1201ms，有的200多ms就过了，说明决定这题快不快就在于哈希函数判重快不快。
注意：空白前面可能也是空白哟。
AC代码： 1201ms
#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>#include <queue>#include<utility>using namespace std;typedef long long LL;typedef pair<int, int> PI;typedef int state[4][8];const int maxn = 1e6 + 10;const int hash1 = 1000007, hash2 = 1007; //双哈希解决冲突int goal[][8] = {11,12,13,14,15,16,17,0,21,22,23,24,25,26,27,0,31,32,33,34,35,36,37,0,41,42,43,44,45,46,47,0};int st[4][8];int sp[][2] = {0,0,1,0,2,0,3,0};struct node{int pip;int next;node() {}node(int pip, int next): pip(pip), next(next){}}HASH[maxn];int head[maxn];struct card{int a[4][8];int pos[4][2]; //四个空位int step;card() {}card(int b[][8], int p[][2], int step):step(step) {memcpy(a, b, sizeof(a));memcpy(pos, p, sizeof(pos));}};PI get_hash(int a[][8]) {LL h1 = 0, h2 = 0;for(int i = 0; i < 4; ++i)for(int j = 0; j < 8; ++j) {h1 = (h1 * 100 + a[i][j]) % hash1;h2 = (h2 * 100 + a[i][j]) % hash2;}return make_pair((int)h1, (int)h2);}int cur = 0;bool Insert(PI pi) {int h = pi.first, val = pi.second;int u = head[h];while(u != -1) {if(val == HASH[u].pip) return false;u = HASH[u].next;}HASH[cur] = node(val, head[h]);head[h] = cur;cur++;return true;}int find(int a[][8], int key) {for(int i = 0; i < 4; ++i)for(int j = 0; j < 8; ++j) {if(a[i][j] == key) return i * 8 + j;}}int bfs() {memset(head, -1, sizeof(head));queue<card>q;q.push(card(st, sp, 0));PI pi = get_hash(st);Insert(pi);while(!q.empty()) {card cd = q.front();q.pop();state &a = cd.a;if(!memcmp(goal, a, sizeof(goal))) return cd.step;for(int i = 0; i < 4; ++i) {int x = cd.pos[i][0], y = cd.pos[i][1];int val = a[x][y - 1];if(val == 0 || val % 10 == 7) continue;int pos = find(a, val + 1);int px = pos / 8, py = pos % 8;swap(a[x][y], a[px][py]);PI pi = get_hash(a);if(!Insert(pi)) { //判重swap(cd.a[x][y], cd.a[px][py]);continue;}cd.pos[i][0] = px, cd.pos[i][1] = py;cd.step++;q.push(cd);cd.pos[i][0] = x, cd.pos[i][1] = y;swap(a[x][y], a[px][py]);cd.step--;}}return -1;}int f[] = {11,21,31,41};int main() {int T;scanf("%d", &T);while(T--) {cur = 0;for(int i = 0; i < 4; ++i)for(int j = 0; j < 8; ++j) {if(j == 0) st[i][j] = 0;else scanf("%d", &st[i][j]); }for(int i = 0; i < 4; ++i) {for(int j = 1; j < 8; ++j) {switch(st[i][j]) {case 11: swap(st[i][j], st[0][0]); sp[0][0] = i, sp[0][1] = j; break;case 21: swap(st[i][j], st[1][0]); sp[1][0] = i, sp[1][1] = j; break;case 31: swap(st[i][j], st[2][0]); sp[2][0] = i, sp[2][1] = j; break;case 41: swap(st[i][j], st[3][0]); sp[3][0] = i, sp[3][1] = j; break;}}}printf("%d\n", bfs());}return 0;}
如有不当之处欢迎指出！
