HDU - 1067 Gap (bfs + hash) [kuangbin带你飞]专题二
2024-10-18 00:10:53
题意: 起初定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; }
如有不当之处欢迎指出!
最新文章
- STL的std::find和std::find_if
- C#进阶系列——WebApi 身份认证解决方案:Basic基础认证
- http错误代码含义中英文对照
- Promise编程基础
- java读取记事本文件的部分数据添加到mysql
- ABAP 搜索帮助
- HttpClient 操作总结
- android 使用Scroller实现缓慢移动
- 产生AJAX跨域问题的原因
- delphi 线程教学第七节:在多个线程时空中,把各自的代码塞到一个指定的线程时空运行
- kubernetes系列11—PV和PVC详解
- 方法总结:如何实现html页面自动刷新
- hadoop的缺点
- 2.在Jenkins中配置及执行 maven + selenium + testng项目
- mvc core2.1 Identity.EntityFramework Core 登录 (三)
- 20135327郭皓——Linux内核分析第二周 操作系统是如何工作的
- Hbase操作table常见方法示例
- Flink HA
- multiprocess(上)
- ls 的详细使用