Eight
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1043/http://acm.split.hdu.edu.cn/showproblem.php?pid=1043
IDA*
八数码问题直接dfs/bfs，时间复杂度很高，需要一个很好的剪枝，使用IDA*。当前状态到达目标状态最短（理想）距离h是各个数字直接到达目的地，如果h+当前步数>最深搜索的步数，那么这种情况就不去考虑。对于判断八数码是否可解，需要用到逆序数的知识（(╯‵□′)╯︵┻━┻这谁会知道啊）：x的移动并不影响整个数列逆序数的奇偶性，也就是说若给定初始状态逆序数的奇偶性与目标状态不同，则unsolvable。去重用到了状态压缩，因为数字数量级为10^9，使用set/map存储状态。（坑点是多组数据，但是题目没说）
代码如下：
#include<cstdio>
#include<cmath>
#include<iostream>
#include<set>
using namespace std;
const int standard=;
set<int>exist;
int a[],state[][],deep,sx,sy,step[];
char c;
int dx[]={,,-,};
int dy[]={-,,,};
char towards[]={'l','r','u','d'};
int index;
bool ok=;
int inversions(){//求逆序数
int num=;
for(int i=;i<;++i)
for(int j=i+;j<;++j)
if(a[i]!=&&a[j]!=)
if(a[j]<a[i])num++;
return num;
}
int zip(){
int s=;
for(int i=;i<;++i)
for(int j=;j<;++j)
s=s*+state[i][j];
return s;
}
int Astar(){//无视障碍物直接到达目的地所需步数
int h=;
for(int i=;i<;++i)
for(int j=;j<;++j){
int num=state[i][j];
if(num!=){
int x=(num-)/;
int y=(num-)%;
h+=abs(x-i)+abs(y-j);
}
}
return h;
}
void IDAstar(int px,int py,int nowdeep){
if(ok)return;
int h=Astar();
if(!h&&zip()==standard){
ok=;
return;
}
if(nowdeep+h>deep)return;//A*估价函数
for(int i=;i<;++i){
int x=px+dx[i];
int y=py+dy[i];
if(<=x&&x<&&<=y&&y<){
swap(state[px][py],state[x][y]);
int s=zip();
if(!exist.count(s)){
step[index++]=i;
exist.insert(s);
IDAstar(x,y,nowdeep+);
if(ok)return;
exist.erase(s);
step[--index]=;
}
swap(state[px][py],state[x][y]);
}
}
}
int main(void){
char k;
while(cin>>k){
ok=;
index=;
for(int i=;i<;++i){
if(i==)c=k;
else cin>>c;
if(''<=c&&c<='')
a[i]=c-'';
else a[i]=;
}
if(inversions()&){//若有解，逆序数的奇偶性和standard相同
cout<<"unsolvable"<<endl;
continue;
}
for(int i=;i<;++i)
for(int j=;j<;++j){
state[i][j]=a[*i+j];
if(state[i][j]==)
sx=i,sy=j;
}
int s=zip();
if(s==standard){
cout<<""<<endl;
continue;
}
for(deep=;!ok;++deep){
exist.clear();
exist.insert(s);
IDAstar(sx,sy,);
}
for(int i=;i<index;++i)
cout<<towards[step[i]];
cout<<""<<endl;
}
}
随机推荐
-
openldap加密传输sssd
http://blog.father.gedow.net/2015/09/29/sssd-ldap-sudo/ yum -y install openldap-clients sssd authcon ...
-
Spring进阶教程之在ApplicationContext初始化完成后重定义Bean
前言 很久没有写博客了,也是两个原因:一是自己觉得一直在班门弄斧,其实自己没什么技术可言:二是很多朋友的问题实际上可以自行解决,我经常觉得不该我来过问,或者是有时候我认为技术还得靠自己钻研,我一两句话 ...
-
umask setuid setgid
cat /etc/bashrc if [ $UID -gt 199 ] && [ "`id -gn`" = "`id -un`" ];#用户UI ...
-
tar 报错gzip: stdin: not in gzip format
今天在linux下 用tar -zxvf xxx.tar.bz2 然后就报这个错. gzip: stdin: not in gzip formattar: Child returned status ...
-
判断数据库内容，在页面显示自定义数据case when
判断数据库内容,在页面显示自定义数据 case when...then ...else...end 比如:数据库内容是这样: 通过sql语句判断,数据库的name字段,内容是月桂的,显示嫦娥,其他的显 ...
-
Spring RESTFul Client – RestTemplate Example--转载
原文地址:http://howtodoinjava.com/2015/02/20/spring-restful-client-resttemplate-example/ After learning ...
-
ubuntu安装spyder和jupyter notebook
ubuntu安装spyder和jupyter notebook 安装spyder 安装spyder sudo apt install spyder sudo apt install spyder3 安 ...
-
测试 多线程 实现 callable 带返回值
package threadTest; import java.util.ArrayList; import java.util.Date; import java.util.concurrent.C ...
-
在Ubuntu上安装pyenv 相关问题Common build problems
Requirements: Ubuntu/Debian: sudo apt-get install -y make build-essential libssl-dev zlib1g-dev libb ...
-
结合File类浅析递归的使用
递归算法就是方法自身直接或者间接地调用到了自身,它是一种写起来很简单,但理解起来不那么简单的算法. 一个功能在被重复地调用,并且运算的结果和上一次的调用有关, 这种时候,可以使用递归. * 注意: * ...