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 322560
using namespace std; struct Node
{
int a[],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[]={,,,,,,,,};
int vis[],pre[],dis[] = {-,-,,};
int a[][]; int get_Hash(Node x)
{
int ans = ;
for(int i = ;i < ;i++)
{
int k = ;
for(int j =;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=;
for(int i=;i<;i++)
{
if(x.a[i] == ) continue;
ans += abs(i/-(x.a[i]-)/)+abs(i%-(x.a[i]-)%);
}
return ans;
} void printff(int h)
{
if(pre[h] == -) return;
printff(pre[h]);
switch (vis[h])
{
case : printf("u");
break;
case : printf("l");
break;
case : printf("d");
break;
case : printf("r");
break;
}
}
int main()
{
char str[];
while(gets(str))
{
memset(vis,-,sizeof(vis));
memset(pre,-,sizeof(pre));
int now = ,num = ;
for(int i = ;i < ;i++)
{
for(int j = ;j < ;j++,now++)
{
if(str[now] >= '' && str[now] <= '')
{
start.a[num++] = str[now]-'';
}
else if(str[now] == 'x')
{
start.num = num;
start.a[num++] = ;
}
else j--;
}
} num = ;
for(int i = ;i < ;i++)
{
for(int j = i+;j <;j++)
{
if(start.a[i] && start.a[j] && start.a[i]>start.a[j]) num++;
}
}
if(num%)
{
printf("unsolvable\n");
continue;
}
start.Hash = get_Hash(start);
if(start.Hash == MAX)
{
printf("\n");
continue;
}
start.g = ;
start.h = get_h(start);
vis[start.Hash] = -;
priority_queue<Node> q;
q.push(start);
while(!q.empty())
{
Node temp = q.top();
int xx = temp.num/,yy = temp.num%;
q.pop();
for(int i = ;i < ;i++)
{
Node x = temp;
x.num += dis[i];
if(yy == && i == ) continue;
if(yy == && i == ) continue;
if(x.num < || x.num > ) continue;
swap(x.a[x.num],x.a[temp.num]);
x.Hash = get_Hash(x);
if(vis[x.Hash] != -) 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");
}
}

最新文章

  1. background-size
  2. Symantec Backup Exec 2012 Agent For Linux安装
  3. 监控数据库运行 - MS SQL 日常维护管理常用脚本(二)
  4. maven下读取资源文件的问题(转)
  5. Linux rpmbuild命令
  6. java基础(二十)IO流(三)
  7. 如何给report自定义page number
  8. Android 使用monkey自动测试
  9. Linux C++ 开发简介(包括Linux守护线程)
  10. win10环境下python3.5安装步骤
  11. java面向对象--抽象类和接口
  12. python实现时间o(1)的最小栈
  13. android + php 后台开发
  14. configSections必须是根节点下第一个节点
  15. vue中复选框全选与反选
  16. WPF Image Source 设置相对路径图片
  17. [分享] 采用opencv_cascadetrain进行训练的步骤及注意事项 [复制链接]
  18. Android安全防护防护———Android 端常见的安全问题
  19. angular.copy() 取消angular的数据双向绑定
  20. 网络结构----ISO/OSI七层网络模型和TCP/IP四层网络模型

热门文章

  1. Linux下安装oracle提示INS-20802 Oracle&#160;Net&#160;Configuration&#160;Assistant
  2. centos7+docker+elasticsearch 安装记录+踩坑
  3. git submodule 管理子项目
  4. Quartz.NET总结(八)如何根据自己需要配置Topshelf 服务
  5. JPA或Hibernate中使用原生SQL实现分页查询、排序
  6. Springboot引入本地jar时打包
  7. 软工作业-14组铁大FaceBook网站使用体验
  8. 网鼎杯题目“phone”--十六进制mysql注入
  9. Linux系统终端session保持服务工具-Tmux
  10. Mixing .NET