HDU 1043 ，POJ 1077 Eight - c++编程基础

八数码问题

Input You will receive, several descriptions of configuration of the 8 puzzle. One description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are represented by numbers 1 to 8, plus 'x'. For example, this puzzle

1 2 3
x 4 6
7 5 8

is described by this list:

1 2 3 x 4 6 7 5 8

Output You will print to standard output either the word ``unsolvable'', if the puzzle has no solution, or a string consisting entirely of the letters 'r', 'l', 'u' and 'd' that describes a series of moves that produce a solution. The string should include no spaces and start at the beginning of the line. Do not print a blank line between cases.

Sample Input

2  3  4  1  5  x  7  6  8

Sample Output

ullddrurdllurdruldr

一、数据如何存储和表示？

1、可以用整形来表示八数码的状态，x可以当作“9”，“0”不好处理，例如终态12345678x，可以表示成整数123456789，

2、用数组来存储，这里x可以用0或9来表示。

二、数据如何拓展？

1、对于int型整数，数据的拓展就是对这个数的处理，例如对于整数

1 2 3 1 2 3

4 5 6 4 5 9

7 8 9 x上移一位变成的状态是 7 8 6 即整数123459786

2、对于数组，数据拓展就是将该数组看成是二维数组，对此二维数组行和列的处理

三、如何记录路径？

1、构造一张邻接表，链式或者是连续存储都可以，记录每个节点的父节点和所有子节点，最后从目的节点递归输出最短路径，不用耗费大量内存记录走过的路径，所以极力推荐此种实现方法，具体应用可以参见

LeetCode OJ:Word Ladder II 解题思路过程详谈

2、因为此题只是记录udlr，所以可以用string来记录，不过因为对每个路径都需要存储走过的路径，太耗内存，所以不推荐

四、如何判重？

1、对于int型数组，可以构造一个大数组，记录是否访问，如vis[123456789]表示123456789状态是否访问，优点：快速。缺点：大量数据浪费，int类型大小的局限性

2、对于数组，可以将数组变成int型，再进行操作

3、用map来存，避免大量浪费

4、用康托拓展判重

五、状态转移如何建立？

1、最简单的无非是广搜，

（1）正向广搜

（2）反向广搜，将所有可能点都记录下来，用string[]大数组存储所有路径，当输入数据次数较多时比较适用，因为广搜只进行1次，内存消耗太大

2、双向广搜

3、A*算法

4、IDA*算法

这里提供一个使用双向广搜+map+int型存储数据版，答案不对，仅供参考

#include 
  
   
#include 
    using namespace std; typedef struct{ int x,w; char s; }aaa; aaa dui[500000],du[500000]; char www[500000]; int fang[4][2]={1,0,-1,0,0,1,0,-1}; int jin[9]={100000000,10000000,1000000,100000,10000,1000,100,10,1}; map
    
      a; char w[3][3]; int main() { freopen("C:\\in.txt","r",stdin); for(int i=0;i<3;i++) for(int j=0;j<3;j++) cin>>w[i][j]; int many,ji,ji1,zan,zan2,x,y,tt,ww,ta,wa,q; many=0; char w2[9]; for(int i=0;i<3;i++) for(int j=0;j<3;j++) w2[many++]=w[i][j]; many=0; for(int i=0;i<3;i++) for(int j=0;j
     
      =0 &&y+fang[i][1]<3&&y+fang[i][1]>=0&&neng==false){ s=dui[tt].w; zan=s/jin[ji]; zan2=s/jin[(x+fang[i][0])*3+(y+fang[i][1])]; zan=zan%10; zan2=zan2%10; s=s-zan*jin[ji]-zan2*jin[(x+fang[i][0])*3+(y+fang[i][1])]; s=s+zan2*jin[ji]+zan*jin[(x+fang[i][0])*3+(y+fang[i][1])]; if(a[s]!=1){ if(a[s]==2) neng=true; a[s]=1; ww++; dui[ww].w=s; dui[ww].x=tt; if(i==0) dui[ww].s='d'; if(i==1) dui[ww].s='u'; if(i==2) dui[ww].s='r'; if(i==3) dui[ww].s='l'; } } x=ji1/3; y=ji1%3; if(x+fang[i][0]<3&&x+fang[i][0]>=0 &&y+fang[i][1]<3&&y+fang[i][1]>=0&&neng==false){ s=du[ta].w; zan=s/jin[ji1]; zan2=s/jin[(x+fang[i][0])*3+(y+fang[i][1])]; zan=zan%10; zan2=zan2%10; s=s-zan*jin[ji1]-zan2*jin[(x+fang[i][0])*3+(y+fang[i][1])]; s=s+zan2*jin[ji1]+zan*jin[(x+fang[i][0])*3+(y+fang[i][1])]; if(a[s]==0){ a[s]=2; wa++; du[wa].w=s; du[wa].x=ta; if(i==0) du[wa].s='u'; if(i==1) du[wa].s='d'; if(i==2) du[wa].s='l'; if(i==3) du[wa].s='r'; } } } ta++; tt++; } ji=0; q=ww; while(q!=1){ ji++; www[ji]=dui[q].s; q=dui[q].x; } for(int i=ji;i>=1;i--) printf("%c",www[i]); ji=0; q=1; while(du[q].w!=dui[ww].w) q++; while(q!=1){ ji++; www[ji]=du[q].s; q=du[q].x; } for(int i=1;i<=ji;i++) printf("%c",www[i]); printf("\n"); } else printf("unsolvable\n"); return 0; }

再提供一个反向广搜版+康托版

/*
HDU 1043 Eight
思路：反向搜索，从目标状态找回状态对应的路径
用康托展开判重

*/
#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        using namespace std; const int MAXN=1000000;//最多是9!/2 int fac[]={1,1,2,6,24,120,720,5040

HDU 1043 ，POJ 1077 Eight(一)

LeetCode OJ:Word Ladder II 解题思路过程详谈