Eight

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 11243 Accepted Submission(s): 3022
Special Judge

Problem Description

The 15-puzzle has been around for over 100 years; even if you don't know it by that name, you've seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing. Let's call the missing tile 'x'; the object of the puzzle is to arrange the tiles so that they are ordered as:

1  2  3  4  5  6  7  8  9 10 11 12 13 14 15  x

where the only legal operation is to exchange 'x' with one of the tiles with which it shares an edge. As an example, the following sequence of moves solves a slightly scrambled puzzle:

1  2  3  4     1  2  3  4     1  2  3  4     1  2  3  4  5  6  7  8     5  6  7  8     5  6  7  8     5  6  7  8  9  x 10 12     9 10  x 12     9 10 11 12     9 10 11 12 13 14 11 15    13 14 11 15    13 14  x 15    13 14 15  x             r->            d->            r->

The letters in the previous row indicate which neighbor of the 'x' tile is swapped with the 'x' tile at each step; legal values are 'r','l','u' and 'd', for right, left, up, and down, respectively.

Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and

frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing 'x' tile, of course).

In this problem, you will write a program for solving the less well-known 8-puzzle, composed of tiles on a three by three

arrangement.

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

　　题意：经典的八数码，给出当前状态，求出恢复到从小到大排列的顺序的任意一种路径，如果不存在就输出unsolvable。这一题用搜索解决。在看到其他人的题解看到这一题有很多种解法，这里我尝试的是用A*，第一次用A*→_→。

　　先说说解法，这一题需要先知道的知识：①对于八数码有解的情况，用当前的八个数字组成的序列，如果逆序对的对数是偶数的话就有解，否则无解，这是判断八数码有没有解的条件。②这里如果选择使用哈希记录状态的话，需要想个不错的方法。这里使用的方法是用康托展开。对于这东西可以自行百度一下。

　　这里使用A*，需要注意的是，我们选择扩展的状态是选择f(s)(估值函数)最小的状态。其中在计算g(s)(已使用代价)用的是每扩展一次就加一，h(s)(预估使用代价)是使用每一个位置到达正确位置的哈密顿距离之和来作为预估值。在将状态放入优先队列(OPEN表)的时候根据不同顺序比较g(s),h(s)效果可能不一样。

　　A*的本质就是每一次从还没有扩展的状态集合里面选出f(s)最小的那个状态来扩展，感觉看起来就是优先队列版的BFS。

　　当然，A*不一定就能提高效率，这就得看估值函数的选取了。

　　这一题码了两次，第一次是基本上跟着别人的代码写的，第二次自己写，但还是不得不稍微看一些自己写的代码，主要是对康托展开不是很熟悉。

上代码：

1 #include 
       
          2 #include 
        
           3 #include 
         
            4 #include 
          
             5 #include 
           
              6 #define MAX 400002  7 using namespace std;  8 typedef struct Node{  9     int maze[3][3]; 10     int y,x; 11     int hash; 12     int h,g; 13     bool isok(){ 14         return (0<=y && y<3 && 0<=x && x<3); 15     } 16  17     bool operator < (const Node a) const{ 18         if(h>a.h) return 1; 19         if(h==a.h && g>a.g) return 1; 20         return 0; 21     } 22  23 }Node; 24 Node s; 25 const int cantor[9] = {
     1,1,2,6,24,120,720,5040,40320}; 26 const int target = 322560; 27 const int cy[]={
     0,0,1,-1}; 28 const int cx[]={
     1,-1,0,0}; 29 int vis[MAX]; 30 int pre[MAX]; 31 priority_queue
            
              p; 32 bool check(Node c){ 33 int a[9]; 34 int k=0,sum=0; 35 for(int i=0;i<3;i++) for(int j=0;j<3;j++) a[k++]=c.maze[i][j]; 36 for(int i=0;i
             
              a[j]) sum++; 37 return !(sum&1); 38 } 39 40 int getHash(Node c){ 41 int a[9]; 42 int k=0,h=0,sum=0; 43 for(int i=0;i<3;i++) for(int j=0;j<3;j++) a[k++]=c.maze[i][j]; 44 for(int i=0;i
              
               =0;i--) putchar(ss[i]);119 puts("");120 }121 122 int main()123 {124 //freopen("data.txt","r",stdin);125 while(scan()){126 if(!check(s)){127 puts("unsolvable");128 }else{129 s.hash = getHash(s);130 if(s.hash == target){131 puts("");132 }else{133 astar();134 printPath();135 }136 }137 }138 return 0;139 }

HDU 1043

1 #include 
       
          2 #include 
        
           3 #include 
         
            4 #include 
          
             5 #include 
           
              6 #define MAX 400002  7 using namespace std;  8   9 const int cantor[] = {
     1,1,2,6,24,120,720,5040,40320}; 10 const int target = 322560; 11 int vis[MAX],pre[MAX]; 12 int cy[]={
     0,1,0,-1}; 13 int cx[]={
     1,0,-1,0}; 14 typedef struct Node{ 15     int maze[3][3]; 16     int h,g,y,x; 17     int hash; 18  19     bool isok(){ 20         return (0<=y && y<3 && 0<=x && x<3); 21     } 22  23     bool islegal(){ 24         int a[9],k=0,sum=0; 25         for(int i=0;i<3;i++) for(int j=0;j<3;j++) a[k++]=maze[i][j]; 26         for(int i=0;i
            
             a[j]) sum++; 27 return !(sum&1); 28 } 29 30 bool operator < (const Node o)const{ 31 return h==o.h ? g>o.g : h>o.h; 32 } 33 }Node; 34 Node s; 35 priority_queue
             
               q; 36 37 int getHash(Node e){ 38 int a[9],k=0,res=0; 39 for(int i=0;i<3;i++) for(int j=0;j<3;j++) a[k++]=e.maze[i][j]; 40 for(int i=0;i
              
               =0;i--) putchar(ss[i]);102 putchar('\n');103 }104 105 bool get(){106 char ss[100];107 if(gets(ss)){108 int k=0,l=strlen(ss);109 for(int i=0;i<3;i++) for(int j=0;j<3;j++){110 while(k

POJ 1077

转载于:https://www.cnblogs.com/sineatos/p/3840370.html

你可能感兴趣的文章