首页 > 代码库 > HDU_1175_A*
HDU_1175_A*
http://acm.split.hdu.edu.cn/showproblem.php?pid=1043
刚开始一脸蒙逼，看了题解之后，参考了A*算法。
参考：http://www.cnblogs.com/technology/archive/2011/05/26/2058842.html
还用到了变进制Hash全排列来判断结果是否满足条件。
参考：http://www.chinaunix.net/old_jh/23/1283459.html
第一次接触A*，感觉类似BFS，不同的是它可以更快地找到最优解。
最后要注意路径的保存，最终用dfs的printff输出。
#include<iostream>#include<cstring>#include<algorithm>#include<queue>#include<cstdio>#define MAX 322560using namespace std;struct Node{ int a[9],g,h,num,Hash; friend bool operator<(const Node x,const Node y) { return x.h+x.g>y.h+y.g; }}start;int HASH[9]={1,1,2,6,24,120,720,5040,40320};int vis[400000],pre[400000],dis[4] = {-3,-1,3,1};int a[3][3];int get_Hash(Node x){ int ans = 0; for(int i = 0;i < 9;i++) { int k = 0; for(int j =0;j <i;j++) { if(x.a[j]>x.a[i]) k++; } ans += HASH[i]*k; } return ans;}int get_h(Node x){ //»ñµÃ¹À¼Ûº¯ÊýH int ans=0; for(int i=0;i<9;i++) { if(x.a[i] == 0) continue; ans += abs(i/3-(x.a[i]-1)/3)+abs(i%3-(x.a[i]-1)%3); } return ans;}void printff(int h){ if(pre[h] == -1) return; printff(pre[h]); switch (vis[h]) { case 0: printf("u"); break; case 1: printf("l"); break; case 2: printf("d"); break; case 3: printf("r"); break; }}int main(){ char str[50]; while(gets(str)) { memset(vis,-1,sizeof(vis)); memset(pre,-1,sizeof(pre)); int now = 0,num = 0; for(int i = 0;i < 3;i++) { for(int j = 0;j < 3;j++,now++) { if(str[now] >= ‘0‘ && str[now] <= ‘9‘) { start.a[num++] = str[now]-‘0‘; } else if(str[now] == ‘x‘) { start.num = num; start.a[num++] = 0; } else j--; } } num = 0; for(int i = 0;i < 9;i++) { for(int j = i+1;j <9;j++) { if(start.a[i] && start.a[j] && start.a[i]>start.a[j]) num++; } } if(num%2) { printf("unsolvable\n"); continue; } start.Hash = get_Hash(start); if(start.Hash == MAX) { printf("\n"); continue; } start.g = 0; start.h = get_h(start); vis[start.Hash] = -2; priority_queue<Node> q; q.push(start); while(!q.empty()) { Node temp = q.top(); int xx = temp.num/3,yy = temp.num%3; q.pop(); for(int i = 0;i < 4;i++) { Node x = temp; x.num += dis[i]; if(yy == 0 && i == 1) continue; if(yy == 2 && i == 3) continue; if(x.num < 0 || x.num > 8) continue; swap(x.a[x.num],x.a[temp.num]); x.Hash = get_Hash(x); if(vis[x.Hash] != -1) continue; x.g++; x.h = get_h(x); q.push(x); pre[x.Hash] = temp.Hash; vis[x.Hash] = i; if(x.Hash == MAX) goto there; } } there: printff(MAX); printf("\n"); }}
HDU_1175_A*
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。