题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6171
题意: 给你一个高度为6的塔形数组,你每次只能将0与他上下相邻的某个数交换,问最少交换多少次可以变为初始状态,若需要的步数大于20,直接输出too difficult,初始状态为:
0
1 1
2 2 2
3 3 3 3
4 4 4 4 4
5 5 5 5 5 5
解法:两种方法,一种是双向BFS+Hash,另外是A*估价+Hash。
- //双BFS
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 100010;
- const int dir[4][2] = {{-1,-1},{-1,0},{1,0},{1,1}};
- typedef unsigned long long uLL;
- struct node{
- int val[6][6];
- int r, c, k, step;
- };
- map <uLL, int> book[2];
- uLL Hash(node x){
- uLL ret = 0;
- for(int i=0; i<6; i++)
- for(int j=0; j<=i; j++)
- ret = ret*6+x.val[i][j];
- return ret;
- }
- int BFS(node s, node e){
- queue <node> q;
- book[0].clear();
- book[1].clear();
- s.k = 0;
- e.k = 1;
- s.step = e.step = 0;
- book[s.k][Hash(s)] = 0;
- book[e.k][Hash(e)] = 0;
- q.push(s);
- q.push(e);
- while(q.size()){
- node u = q.front(); q.pop();
- uLL tmp = Hash(u);
- if(book[!u.k].count(tmp)){
- if(book[!u.k][tmp]+u.step<=20){
- return book[!u.k][tmp]+u.step;
- }
- else continue;
- }
- if(u.step >= 10) continue;
- for(int i=0; i<4; i++){
- node t = u;
- t.r += dir[i][0];
- t.c += dir[i][1];
- if(t.r >= 6 || t.r < 0 || t.c > t.r || t.c < 0) continue;
- swap(t.val[t.r][t.c], t.val[u.r][u.c]);
- tmp = Hash(t);
- if(book[t.k].count(tmp)) continue;
- t.step++;
- book[t.k][tmp] = t.step;
- q.push(t);
- }
- }
- return -1;
- }
- int main()
- {
- int T;
- scanf("%d", &T);
- while(T--)
- {
- node s,e;
- e.r = e.c = 0;
- for(int i=0; i<6; i++){
- for(int j=0; j<=i; j++){
- scanf("%d", &s.val[i][j]);
- if(!s.val[i][j])
- s.r = i, s.c = j;
- e.val[i][j] = i;
- }
- }
- int ans = BFS(s, e);
- if(ans == -1) puts("too difficult");
- else printf("%d\n", ans);
- }
- return 0;
- }
来源: http://www.cnblogs.com/spfa/p/7454980.html