HDU - 1067 Gap (bfs + hash) [kuangbin带你飞]专题二

  题意：    起初定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;}  如有不当之处欢迎指出！