题意:经典八数码问题

思路:双向bfs

ps:还有a*算法(还不会)等解法。

代码:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std; #define MAXN 362885//最多组合个数:9!=362880 int dir[]={-,,-,};//4个方向移动:u,d,l,r
char opF[]={'u','d','l','r'};//正向bfs操作
char opR[]={'d','u','r','l'};//反向bfs操作
int fac[]={,,,,,,,,};//阶乘
bool visF[MAXN];//正向访问标志
bool visR[MAXN];//
string sTarg="";//目标棋盘 struct node{//存储棋盘信息
string s;//当前棋盘
int xLoca;//x位置
}t; struct node2{//存储操作
int idF,idR;//正向前驱、反向前驱
char cF,cR;//操作
}op[MAXN]; int cantor_hash(string s){//康托展开,一共n位
int n=;//共9位
int i,j,temp,num;
num=;
for(i=;i<n-;i++){//n为位数
temp=;
for(j=i+;j<n;j++){
if(s[j]<s[i])temp++;
}
num+=fac[n-(i+)]*temp;
}
return num;//从0开始
} void display(int i){//输出正向操作
if(op[i].idF==-)return;
display(op[i].idF);
printf("%c",op[i].cF);
} void dBfs(){
queue<node>qF,qR;//正向队列,反向队列
node tmp1,tmp2;//棋盘状态临时变量
int id_hash,id_hash2,xLoca,i;//id 康托哈希下标值,xLoca 暂存x位置 tmp1=t;//初始状态 tmp2.s=sTarg;//目标状态
tmp2.xLoca=;//目标状态x位置 id_hash=cantor_hash(tmp1.s);//初始状态
visF[id_hash]=true;
op[id_hash].idF=-;
qF.push(tmp1); id_hash=cantor_hash(tmp2.s);//目标状态
visR[id_hash]=true;
op[id_hash].idR=-;
qR.push(tmp2); while(!qF.empty()&&!qR.empty()){
//正向bfs
tmp1=qF.front();
qF.pop();
id_hash=cantor_hash(tmp1.s);
if(visR[id_hash]){//反向bfs也访问过
display(id_hash);
id_hash2=id_hash;
while(op[id_hash2].idR!=-){
printf("%c",op[id_hash2].cR);
id_hash2=op[id_hash2].idR;
}
printf("\n");
return;
}
for(i=;i<;++i){
if(i==&&tmp1.xLoca<)continue;
if(i==&&tmp1.xLoca>)continue;
if(i==&&tmp1.xLoca%==)continue;
if(i==&&tmp1.xLoca%==)continue;
xLoca=tmp1.xLoca+dir[i]; tmp2=tmp1;
swap(tmp2.s[tmp1.xLoca],tmp2.s[xLoca]);
id_hash2=cantor_hash(tmp2.s);
if(!visF[id_hash2]){
visF[id_hash2]=true;
tmp2.xLoca=xLoca;
op[id_hash2].idF=id_hash;
op[id_hash2].cF=opF[i];
qF.push(tmp2);
}
} //反向bfs
tmp1=qR.front();
qR.pop();
id_hash=cantor_hash(tmp1.s);
if(visF[id_hash]){//正向bfs也访问过
display(id_hash);
id_hash2=id_hash;
while(op[id_hash2].idR!=-){
printf("%c",op[id_hash2].cR);
id_hash2=op[id_hash2].idR;
}
printf("\n");
return;
}
for(i=;i<;++i){
if(i==&&tmp1.xLoca<)continue;
if(i==&&tmp1.xLoca>)continue;
if(i==&&tmp1.xLoca%==)continue;
if(i==&&tmp1.xLoca%==)continue;
xLoca=tmp1.xLoca+dir[i]; tmp2=tmp1;
swap(tmp2.s[tmp1.xLoca],tmp2.s[xLoca]);
id_hash2=cantor_hash(tmp2.s);
if(!visR[id_hash2]){
visR[id_hash2]=true;
tmp2.xLoca=xLoca;
op[id_hash2].idR=id_hash;
op[id_hash2].cR=opR[i];
qR.push(tmp2);
}
}
}
} int main(){
char str[];//串
int len;//串长度
int i,j,k;//k 第几个数码
int ivsNum;//逆序数
while(~scanf("%[^\n]",str)){
getchar();//吸收回车 memset(visF,false,sizeof(visF));
memset(visR,false,sizeof(visR)); len=strlen(str);
t.s="";
k=;//第几个数码
for(i=;i<len;++i){//处理字符串
if(str[i]!=' '){
if(str[i]=='x'){
t.s=t.s+'';
t.xLoca=k;
}
else t.s=t.s+str[i];
++k;//
}
} ivsNum=;//逆序数初始为0
for(i=;i<;++i){
if(t.s[i]=='')continue;
for(j=;j<i;++j){
if(t.s[j]=='')continue;
if(t.s[j]>t.s[i])++ivsNum;
}
}
if(ivsNum&)printf("unsolvable\n");//逆序数为奇数
else dBfs();//双向bfs
}
return ;
}

最新文章

  1. Github使(zhuang)用(bi)指南
  2. 在线课程笔记&mdash;.NET基础
  3. angular的跨域(angular百度下拉提示模拟)和angular选项卡
  4. zedboard如何从PL端控制DDR读写(六)
  5. Nmap使用指南(1)
  6. iOS自动布局一
  7. MyBatis学习总结_06_调用存储过程
  8. layer.js,,,分享一个好用的弹出层
  9. javascript google map circle radius_changed ,angularjs google map circle radius_changed
  10. Spring Boot 启动原理分析
  11. VB.NET 内存指针和非托管内存的应用
  12. runnable与handler结合使用,其实跟在Thread中的run()中sleep的效果是一样的
  13. Cocos2dx 3.1.1 学习笔记整理(1) 新建项目
  14. javaScript 基本类型之间转换
  15. css变化代码2
  16. URLSearchParams 接口
  17. linux下 gdb+coredump 调试偶发crash的程序
  18. git的入门摸索和入门研究
  19. rpmbuild 源码打包clickhouse,附带打好的rpm包下载地址
  20. (转)新手C#SQL语句的学习2018.08.13

热门文章

  1. win8激活工具,win 8激活工具,windows8激活工具,赶紧来下载咯
  2. Redis的内部运作机制
  3. T3054 高精度练习-文件操作 codevs
  4. 高效的MySQL的批插入 BULK INSERT
  5. 应用程序中的server错误,没有名称为“ServiceBehavior”的服务行为
  6. 【Linux学习笔记】栈与函数调用惯例
  7. linux 进程间通信之 消息队列
  8. android 4.4以上能够实现的沉浸式状态栏效果
  9. pcapReader——源代码分析
  10. CPU Stepping