hdu 1067(hash+bfs)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1067
思路:学会了手写Hash。。。orz....纪念一下。
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<queue>
  6 using namespace std;
  7 #define MAXN 1000007
  8 typedef long long ll;
  9 ll Hash[MAXN];
 10 
 11 struct Node{
 12     int map[4][8],step;
 13     bool operator == (const Node &p) const {
 14         for(int i=0;i<4;i++)
 15             for(int j=0;j<8;j++)
 16                 if(map[i][j]!=p.map[i][j])
 17                     return false;
 18         return true;
 19     }
 20     //手写hash
 21     ll HashValue(){
 22         ll value=0;
 23         for(int i=0;i<4;i++)
 24             for(int j=0;j<8;j++)
 25                 value+=(value<<ll(1))+(ll)map[i][j];
 26         return value;
 27     }
 28 };
 29 
 30 Node Start,End;
 31 
 32 void Initaite(){
 33     memset(Hash,-1,sizeof(Hash));
 34     for(int i=0;i<4;i++){
 35         Start.map[i][0]=0;
 36         for(int j=1;j<8;j++){
 37             scanf("%d",&Start.map[i][j]);
 38         }
 39     }
 40     Start.step=0;
 41 }
 42 
 43 //最后的结果
 44 void GetEnd(){
 45     for(int i=0;i<4;i++){
 46         End.map[i][7]=0;
 47         for(int j=0;j<7;j++){
 48             End.map[i][j]=(i+1)*10+(j+1);
 49         }
 50     }
 51 }
 52 
 53 //取得value的hash值+hash判重
 54 bool HashInsert(ll value){
 55     int v=value%MAXN;
 56     while(Hash[v]!=-1&&Hash[v]!=value){
 57         v+=10;
 58         v%=MAXN;
 59     }
 60     if(Hash[v]==-1){
 61         Hash[v]=value;
 62         return true;
 63     }
 64     return false;
 65 }
 66 
 67 void bfs(){
 68     queue<Node>Q;
 69     Node p,q;
 70     Q.push(Start);
 71     HashInsert(Start.HashValue());
 72     while(!Q.empty()){
 73         p=Q.front();
 74         Q.pop();
 75         for(int i=0;i<4;i++){
 76             for(int j=0;j<8;j++){
 77                 if(!p.map[i][j]){
 78                     q=p;
 79                     q.step++;
 80                     int value=p.map[i][j-1]+1;//找比map[i][j-1]大1的数
 81                     if(value==1||value%10==8)continue;//0或者value为7的不能移动
 82                     int x,y,flag=true;
 83                     for(int k=0;k<4&&flag;k++){
 84                         for(int l=1;l<8&&flag;l++){
 85                             if(p.map[k][l]==value){
 86                                 x=k,y=l;
 87                                 flag=false;
 88                             }
 89                         }
 90                     }
 91                     if(!flag){
 92                         swap(q.map[i][j],q.map[x][y]);
 93                         ll value=q.HashValue();
 94                         //hash判重
 95                         if(HashInsert(value)){
 96                             if(q==End){
 97                                 printf("%d\n",q.step);
 98                                 return ;
 99                             }
100                             Q.push(q);
101                         }
102                     }
103                 }
104             }
105         }
106     }
107     puts("-1");
108 }
109 
110 void Solve(){
111     int k=0;
112     //将11，21,31,41这四个数移到第0列
113     for(int i=0;i<4;i++){
114         for(int j=1;j<8;j++){
115             if(Start.map[i][j]==(k+1)*10+1){
116                 swap(Start.map[i][j],Start.map[k][0]);
117                 k++,i=0,j=0;
118             }
119         }
120     }
121     if(Start==End){
122         puts("0");//前四步不记录总步数
123         return ;
124     }
125     bfs();
126 }
127 
128 int main(){
129     int _case;
130     scanf("%d",&_case);
131     GetEnd();
132     while(_case--){
133         Initaite();
134         Solve();
135     }
136     return 0;
137 }
View Code