本文主要是介绍Gap HDU - 1067，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
点击打开链接
第一次用哈希 感觉和状压就是一回事。。
#include <bits/stdc++.h>
using namespace std;
#define M 1000007struct node
{int t[10][10];int s;
};queue <node> que;
int num[10][10],tar[10][10];
int book[1000010];
int ans;void init();
void bfs();
int judge(int p[][10]);
int gethash(int p[][10]);
void change(int p[][10],int val,int x,int y);int main()
{int t,i,j;init();scanf("%d",&t);while(t--){for(i=1;i<=4;i++){for(j=2;j<=8;j++){scanf("%d",&num[i][j]);if(num[i][j]==11||num[i][j]==21||num[i][j]==31||num[i][j]==41){num[i][j]=0;}}}num[1][1]=11,num[2][1]=21,num[3][1]=31,num[4][1]=41;bfs();printf("%d\n",ans);}return 0;
}void init()
{int i,j;for(i=1;i<=4;i++){for(j=1;j<=7;j++){tar[i][j]=i*10+j;}}return;
}void bfs()
{node cur,tem;int i,j,val;while(!que.empty()) que.pop();memset(book,0,sizeof(book));memcpy(tem.t,num,sizeof(num));tem.s=0;que.push(tem);val=gethash(tem.t);book[val]=1;ans=-1;while(!que.empty()){cur=que.front();que.pop();if(judge(cur.t)){ans=cur.s;return;}for(i=1;i<=4;i++){for(j=2;j<=8;j++){if(cur.t[i][j]==0){if(cur.t[i][j-1]==0||cur.t[i][j-1]==17||cur.t[i][j-1]==27||cur.t[i][j-1]==37||cur.t[i][j-1]==47){continue;}tem=cur;change(tem.t,tem.t[i][j-1]+1,i,j);val=gethash(tem.t);if(book[val]==0){tem.s++;que.push(tem);book[val]=1;}}}}}return;
}int judge(int p[][10])
{int i,j;for(i=1;i<=4;i++){for(j=1;j<=8;j++){if(p[i][j]!=tar[i][j]) return 0;}}return 1;
}int gethash(int p[][10])
{int pre[100];int i,j,k,sum;k=0;for(i=1;i<=4;i++){for(j=1;j<=8;j++){pre[++k]=p[i][j]/10;pre[++k]=p[i][j]%10;}}sum=0;for(i=1;i<=k;i++){sum=((sum%M)*7+pre[i]%M)%M;}return sum;
}void change(int p[][10],int val,int x,int y)
{int i,j;for(i=1;i<=4;i++){for(j=2;j<=8;j++){if(p[i][j]==val){swap(p[i][j],p[x][y]);return;}}}return;
}
这篇关于Gap HDU - 1067的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
