题目地址： http://poj.org/problem?id=2046
一道搜索状态压缩的题目，关键是怎样hash。
AC代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
using namespace std; typedef long long LL;
const int N=2222222;
const LL II=1000000007;
const int M=1000007; struct xh
{
int maps[4][8],step;
}w,e,vv[500000]; int aim[4][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 s[80];
int vis[M]; int gethash(int t[][8])
{
int i,j,k=0,hash=0;
for(i=0;i<4;i++)
for(j=0;j<8;j++)
{
s[k++]=t[i][j]/10;
s[k++]=t[i][j]%10;
//转化成数字，hash
}
for(i=0;i<k;i++)//hash
{
hash=hash*7+s[i];
}
hash=(hash&0x7fffffff)%M;
return hash;
} void chang(int num,int i,int j)
{
int a,b;
for(a=0;a<4;a++)
for(b=1;b<8;b++)
{
if(w.maps[a][b]==num)
{
swap(w.maps[a][b],w.maps[i][j]);
return ;
}
}
} bool test(xh a)
{
int i,j;
for(i=0;i<4;i++)
for(j=0;j<8;j++)
if(a.maps[i][j]!=aim[i][j])
return false;
return true;
} void bfs()
{
int i,j,hash,head=0,tail=0;
memset(vis,false,sizeof(vis));
w.maps[0][0]=11;
w.maps[1][0]=21;
w.maps[2][0]=31;
w.maps[3][0]=41;
w.step=0;
vv[tail++]=w;
hash=gethash(w.maps);
vis[hash]=true;
while(head!=tail)
{
e=vv[head++];
if(test(e))
{
printf("%d\n",e.step);
return ;
}
for(i=0;i<4;i++)
for(j=1;j<8;j++)
{
w=e;
if(w.maps[i][j]!=0) continue;
int num=w.maps[i][j-1];//前一个
if(num==0||num==17||num==27||num==37||num==47) continue;
chang(num+1,i,j);
hash=gethash(w.maps);
if(!vis[hash])
{
vis[hash]=true;
w.step++;
vv[tail++]=w;
}
}
}
printf("-1\n");
} int main()
{
int i,j,T,k;
cin>>T;
while(T--)
{
memset(w.maps,0,sizeof(w.maps));
for(i=0;i<4;i++)
for(j=1;j<8;j++)
{
scanf("%d",&k);
w.maps[i][j]=k;
if(k==11||k==21||k==31||k==41)
w.maps[i][j]=0;
}
bfs();
}
return 0;
}