题目链接：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。
双向搜索参考：http://blog.csdn.net/cillyb/article/details/77587228
//双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;
}
放一个队友的A*搜索：
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long uLL;
int lowPos[6][6];
pair<int, int> ppPos[22];
const int dir[4][2] = {{-1, -1}, {-1, 0}, {1, 0}, {1, 1}};
void init()
{
int jsq = 0;
int now = 0;
for(int i = 0; i < 6; i++)
for(int j = 0; j <= i; j++)
{
lowPos[i][j] = now;
ppPos[jsq] = make_pair(i, j);
jsq ++;
now += 3;
}
}
void setStatus(uLL &status, int x, int y, uLL val)
{
int pos = lowPos[x][y];
status &= ~(1ULL << pos);
status &= ~(1ULL << pos + 1);
status &= ~(1ULL << pos + 2);
status |= val << pos;
return;
}
void swapStatus(uLL &status, int a, int b, int x, int y)
{
int pos1 = lowPos[a][b];
int pos2 = lowPos[x][y];
uLL val1 = status >> pos1 & 7;
uLL val2 = status >> pos2 & 7;
status &= ~(1ULL << pos1);
status &= ~(1ULL << pos1 + 1);
status &= ~(1ULL << pos1 + 2);
status &= ~(1ULL << pos2);
status &= ~(1ULL << pos2 + 1);
status &= ~(1ULL << pos2 + 2);
status |= val1 << pos2;
status |= val2 << pos1;
}
pair<int, int> getZeroPos(uLL status)
{
for(int i = 0; i < 21; i++)
{
uLL val = status & 7;
if(val == 0)
return ppPos[i];
status >>= 3;
}
}
int Compare(uLL endStatus, uLL nowStatus)
{
int ret = 0;
for(int i = 0; i < 21; i++)
{
uLL val1 = endStatus & 7;
uLL val2 = nowStatus & 7;
if(val1 != val2)
ret++;
endStatus >>= 3;
nowStatus >>= 3;
}
return ret;
}
int main()
{
init();
int T;
scanf("%d", &T);
while(T--)
{
uLL startStatus = 0;
for(int i = 0; i < 6; i++)
for(int j = 0; j <= i; j++)
{
int x;
scanf("%d", &x);
setStatus(startStatus, i, j, x);
}
uLL endStatus = 0;
for(int i = 0; i < 6; i++)
for(int j = 0; j <= i; j++)
setStatus(endStatus, i, j, i);
queue<uLL> q;
unordered_map<uLL, int> mp;
mp[startStatus] = 0;
q.emplace(startStatus);
while(!q.empty())
{
uLL u = q.front();
q.pop();
if(u == endStatus)
break;
int d = mp[u];
if(d == 20)
break;
pair<int, int> zpos = getZeroPos(u);
int i = zpos.first;
int j = zpos.second;
for(int k = 0; k < 4; k++)
{
int x = i + dir[k][0];
int y = j + dir[k][1];
if(x < 0 || x > 5 || y < 0 || y > x)
continue;
uLL newStatus = u;
swapStatus(newStatus, i, j, x, y);
if(mp.count(newStatus))
continue;
mp[newStatus] = d + 1;
int famly = Compare(endStatus, newStatus);
if(famly + d + 2 > 20)
continue;
q.emplace(newStatus);
}
}
if(mp.count(endStatus) == 0)
puts("too difficult");
else
printf("%d\n", mp[endStatus]);
}
return 0;
}