首页 > 代码库 > HDU - 1043 - Eight / POJ - 1077 - Eight

HDU - 1043 - Eight / POJ - 1077 - Eight

先上题目:

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 <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <queue>  5 #include <algorithm>  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<Node> 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<k;i++) for(int j=i+1;j<k;j++) if(a[i] && a[j] && a[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<k;i++){ 45         sum=0; 46         for(int j=0;j<i;j++){ 47             if(a[i]<a[j]) sum++; 48         } 49         h+=sum*cantor[i]; 50     } 51     return h; 52 } 53  54 int getH(Node c){ 55     int res=0; 56     for(int i=0;i<3;i++) for(int j=0;j<3;j++){ 57         res+=abs(i-(c.maze[i][j]-1)/3)+abs(j-(c.maze[i][j]-1)%3); 58     } 59     return res; 60 } 61  62 void astar(){ 63     while(!p.empty()) p.pop(); 64     memset(vis,-1,sizeof(vis)); 65     memset(pre,-1,sizeof(pre)); 66     Node u,v; 67     s.h = getH(s); 68     p.push(s); 69     vis[s.hash]=-2; 70     while(!p.empty()){ 71         u = p.top(); 72         p.pop(); 73         for(int i=0;i<4;i++){ 74             v=u;v.y+=cy[i];v.x+=cx[i]; 75             if(!v.isok()) continue; 76             swap(v.maze[v.y][v.x],v.maze[u.y][u.x]); 77             if(!check(v)) continue; 78             v.hash = getHash(v); 79             if(vis[v.hash]!=-1) continue; 80             vis[v.hash]=i;  pre[v.hash]=u.hash; 81             v.g++; 82             v.h=getH(v); 83             p.push(v); 84             if(v.hash == target) return ; 85  86         } 87     } 88  89 } 90  91 bool scan(){ 92     char ch[100]; 93     if(!gets(ch)) return 0; 94     int k=0,l=strlen(ch); 95     for(int i=0;i<3;i++) for(int j=0;j<3;j++){ 96         while(k<l && ch[k]== ) k++; 97         if(ch[k]==x){ 98             s.maze[i][j]=0; 99             s.y=i; s.x=j;100         }101         else s.maze[i][j]=ch[k]-0;102         k++;103     }104     return 1;105 }106 107 void printPath(){108     string ss;109     ss.clear();110     int next = target;111     while(pre[next]!=-1){112         if(vis[next]==0) ss+=r;113         else if(vis[next]==1) ss+=l;114         else if(vis[next]==2) ss+=d;115         else ss+=u;116         next = pre[next];117     }118     for(int i=(int)ss.length()-1;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 <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <algorithm>  5 #include <queue>  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<k;i++) for(int j=i+1;j<k;j++) if(a[i] && a[j] && a[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<Node> 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<k;i++){ 41         int t=0; 42         for(int j=0;j<i;j++) if(a[i]<a[j]) t++; 43         res+=t*cantor[i]; 44     } 45     return res; 46 } 47  48 int getH(Node e){ 49     int res=0; 50     for(int i=0;i<3;i++) for(int j=0;j<3;j++){ 51         res+=abs(i-(e.maze[i][j]-1)/3)+abs(j-(e.maze[i][j]-1)%3); 52     } 53     return res; 54 } 55  56 void astar(){ 57     Node u,v; 58     while(!q.empty()) q.pop(); 59     memset(vis,-1,sizeof(vis)); 60     memset(pre,-1,sizeof(pre)); 61     s.g=0; 62     s.h=getH(s); 63     q.push(s); 64     vis[s.hash]=-2; 65     while(!q.empty()){ 66         u=q.top(); 67         q.pop(); 68         //cout<<u.hash<<endl; 69         for(int i=0;i<4;i++){ 70             v=u;v.y+=cy[i];v.x+=cx[i]; 71             if(v.isok()){ 72                 swap(v.maze[v.y][v.x],v.maze[u.y][u.x]); 73                 if(v.islegal()){ 74                     v.hash = getHash(v); 75                     if(vis[v.hash]==-1){ 76                         vis[v.hash]=i; 77                         pre[v.hash]=u.hash; 78                         v.g++;  v.h=getH(v); 79                         q.push(v); 80                         if(v.hash == target) return ; 81                     } 82                 } 83  84             } 85         } 86     } 87 } 88  89 void printPath(){ 90     string ss=""; 91     int next=target; 92     while(pre[next]!=-1){ 93         switch(vis[next]){ 94             case 0:ss+=r;break; 95             case 1:ss+=d;break; 96             case 2:ss+=l;break; 97             case 3:ss+=u;break; 98         } 99         next=pre[next];100     }101     for(int i=(int)ss.length()-1;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<l && ss[k]== ) k++;111             if(ss[k]==x){112                 s.maze[i][j]=0;113                 s.y=i; s.x=j;114             }else s.maze[i][j]=ss[k]-0;115             k++;116         }117         return 1;118     }119     return 0;120 121 }122 123 int main()124 {125     //freopen("data.txt","r",stdin);126     while(get()){127         if(s.islegal()){128             s.hash = getHash(s);129             if(s.hash == target) puts("");130             else{131                 astar();132                 printPath();133             }134         }else puts("unsolvable");135     }136     return 0;137 }
POJ 1077