本文主要是介绍HDU 1043 搜索+康托展开，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
反向搜索 然后把所有的状态都打表出来
用康托展开记录hash判重
#include "string"
#include "iostream"
#include "algorithm"
#include "queue"
using namespace std;const int maxn=1000001;
struct node
{int s[9];int loc; //0的位置int status; // 康托展开的hash值} ncur;int fac[]={1,1,2,6,24,120,720,5040,40320,362880};
int dir[4][2]={1,0,-1,0,0,1,0,-1};
char indexs[5]="udlr";
int aim=46234;
string path[maxn];
int hash[maxn];int Cantor(int s[])
{int sum,i,cnt,j;sum=0;for (i=0;i<9;i++){cnt=0;for (j=i+1;j<9;j++)if (s[i]>s[j])cnt++;sum+=cnt*fac[9-i-1];}return sum+1;
}void BFS()
{queue<node>q;node cur,next;int i,x,y,tx,ty;memset(hash,0,sizeof(hash));for (i=0;i<8;i++) cur.s[i]=i+1;cur.s[8]=0;cur.loc=8;cur.status=aim;q.push(cur);while (!q.empty()){cur=q.front();q.pop();x=cur.loc/3;y=cur.loc%3;for (i=0;i<4;i++){tx=x+dir[i][0];ty=y+dir[i][1];if (tx<0 || tx>2 || ty<0 || ty>2) continue;next=cur;next.loc=tx*3+ty;next.s[cur.loc]=next.s[next.loc];next.s[next.loc]=0;next.status=Cantor(next.s);if (hash[next.status]==0){q.push(next);path[next.status]=indexs[i]+path[cur.status];hash[next.status]=1;}}}
}int main()
{char str[101];int k,i;BFS();while (gets(str)){k=i=0;while (i!=9){while (str[k]==' ') k++;if (str[k]=='x'){ncur.loc=i;ncur.s[i]=0;}else ncur.s[i]=str[k]-'0';k++;i++;}ncur.status=Cantor(ncur.s);if (hash[ncur.status]==1)cout<<path[ncur.status]<<endl;else cout<<"unsolvable"<<endl;}return 0;
}
另一种记录路径的方法，不用string型
#include "stdio.h"
#include "string.h"
#include "queue"
using namespace std;const int dir[4][2]={ {1,0},{-1,0},{0,1},{0,-1} };
const int fac[]={1,1,2,6,24,120,720,5040,40320,362880};
const int aim=46234;
const char indexs[]="udlr";
char path[500010];
int pri[500010],used[500010];
struct node
{int status,loc;int s[9];
} ncur;int Cantor(int b[])
{int sum,cnt,i,j;sum=0;for (i=0;i<9;i++){cnt=0;for (j=i+1;j<9;j++)if (b[i]>b[j]) cnt++;sum+=cnt*fac[9-i-1];}return sum+1;
}
void BFS()
{queue<node>q;node cur,next;int i,x,y,xx,yy;for (i=0;i<8;i++)cur.s[i]=i+1;cur.s[8]=0;cur.loc=8;cur.status=aim;memset(used,0,sizeof(used));used[cur.status]=1;q.push(cur);while (!q.empty()){cur=q.front();q.pop();x=cur.loc/3;y=cur.loc%3;for (i=0;i<4;i++){xx=x+dir[i][0];yy=y+dir[i][1];if (xx<0 || xx>2 || yy<0 || yy>2) continue;next=cur;next.loc=xx*3+yy;next.s[cur.loc]=next.s[next.loc];next.s[next.loc]=0;next.status=Cantor(next.s);if (used[next.status]==0){used[next.status]=1;q.push(next);path[next.status]=indexs[i];pri[next.status]=cur.status;}}}
}void output(int x)
{if (x==aim) return ;printf("%c",path[x]);output(pri[x]);
}
int main()
{char ch[10];int i;BFS();while (scanf("%s",ch)!=EOF){if (ch[0]=='x' ){ncur.s[0]=0;ncur.loc=0;}elsencur.s[0]=ch[0]-'0';for (i=1;i<=8;i++){scanf("%s",ch);if (ch[0]=='x'){ncur.s[i]=0;ncur.loc=i;}elsencur.s[i]=ch[0]-'0';}ncur.status=Cantor(ncur.s);if (used[ncur.status]==0) printf("unsolvable\n");else{output(ncur.status);printf("\n");}}return 0;
}
这篇关于HDU 1043 搜索+康托展开的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
