hdu 1043 Eight

Eight

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 25454 Accepted Submission(s): 6781
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

Source

South Central USA 1998 (Sepcial Judge Module By JGShining)

bfs+优先队列

  1 # include<string.h>
  2 # include<queue>
  3 # define N 363000
  4 using namespace std;
  5 bool visit[N];
  6 char visit1[N];
  7 int pre[N],st,a[10],ed;
  8 int dir[9]={1,1,2,6,24,120,720,5040,40320};
  9 struct node{
 10     int ma[10];
 11     int ans1;
 12     int x;
 13     int f;
 14     int g;
 15     bool operator <(const node &a)const {
 16         return a.f < f;//优先访问f较小者
 17     }
 18 };
 19 int hsh(int s[])
 20 {
 21     int i,j,cnt,sum;
 22     sum=0;
 23     for(i=1;i<=9;i++)
 24     {
 25         cnt=0;
 26         for(j=1;j<i;j++)
 27             if(s[j]>s[i]) cnt++;
 28             sum+=cnt*dir[i-1];
 29     }
 30     return sum;
 31 }
 32 int ABS(int x) {return x<0?(-x):x;}
 33 int h(int s[])//不算x时的曼哈顿距离
 34 {
 35     int curx,cury,endx,endy,sum,i,ans;
 36     sum=0;
 37     for(i=1;i<=9;i++)
 38     {
 39         if(s[i]==9) continue;
 40         ans=s[i];
 41         curx=(i+2)/3;
 42         cury=(i-1)%3+1;
 43         endx=(ans+2)/3;
 44         endy=(ans-1)%3+1;
 45         sum=sum+ABS(curx-endx)+ABS(cury-endy);
 46     }
 47     return sum;
 48 }
 49 void bfs()
 50 {
 51     int ans,i;
 52     priority_queue<node>q;
 53     node cur,next;
 54     cur.ans1=st=hsh(a);
 55     visit[cur.ans1]=1;
 56     if(st==ed) return;
 57     for(i=1;i<=9;i++)
 58     {
 59         cur.ma[i]=a[i];
 60         if(a[i]==9) cur.x=i;
 61     }
 62     cur.g=0;//表示深度
 63     cur.f=h(a);
 64     q.push(cur);
 65     while(!q.empty())
 66     {
 67         cur=q.top();
 68         q.pop();
 69         if((cur.x+2)/3!=1) //向上翻
 70         {
 71             next=cur;
 72             next.x=cur.x-3;
 73             next.ma[cur.x]=next.ma[next.x];
 74             next.ma[next.x]=9;
 75             ans=hsh(next.ma);
 76             if(!visit[ans])
 77             {
 78                 next.g++;
 79                 next.f=next.g+h(next.ma);
 80                 visit[ans]=1;
 81                 next.ans1=ans;
 82                 pre[ans]=cur.ans1;
 83                 visit1[ans]='u';
 84                 if(ans==ed) return;
 85                 q.push(next);
 86             }
 87         }
 88         if((cur.x+2)/3!=3)//向下翻
 89         {
 90             next=cur;
 91             next.x=cur.x+3;
 92             next.ma[cur.x]=next.ma[next.x];
 93             next.ma[next.x]=9;
 94             ans=hsh(next.ma);
 95             if(!visit[ans])
 96             {
 97                 next.g++;
 98                 next.f=next.g+h(next.ma);
 99                 visit[ans]=1;
100                 next.ans1=ans;
101                 pre[ans]=cur.ans1;
102                 visit1[ans]='d';
103                 if(ans==ed) return;
104                 q.push(next);
105             }
106         }
107         if(cur.x%3!=1)//向左翻
108         {
109             next=cur;
110             next.x=cur.x-1;
111             next.ma[cur.x]=next.ma[next.x];
112             next.ma[next.x]=9;
113             ans=hsh(next.ma);
114             if(!visit[ans])
115             {
116                 next.g++;
117                 next.f=next.g+h(next.ma);
118                 visit[ans]=1;
119                 next.ans1=ans;
120                 pre[ans]=cur.ans1;
121                 visit1[ans]='l';
122                 if(ans==ed) return;
123                 q.push(next);
124             }
125         }
126         if(cur.x%3!=0)//向右翻
127         {
128             next=cur;
129             next.x=cur.x+1;
130             next.ma[cur.x]=next.ma[next.x];
131             next.ma[next.x]=9;
132             ans=hsh(next.ma);
133             if(!visit[ans])
134             {
135                 next.g++;
136                 next.f=next.g+h(next.ma);
137                 visit[ans]=1;
138                 next.ans1=ans;
139                 pre[ans]=cur.ans1;
140                 visit1[ans]='r';
141                 if(ans==ed) return;
142                 q.push(next);
143             }
144         }
145     }
146 }
147 int check(int s[])
148 {
149     int i,j,cnt=0;
150     for(i=1;i<=9;i++)
151     {
152         if(s[i]==9) continue;
153         for(j=1;j<i;j++)
154         {
155             if(s[j]==9) continue;
156             if(s[j]>s[i]) cnt++;
157         }
158     }
159     return cnt;
160 }
161 int main()
162 {
163     int i,j,ans;
164     char str[50];
165     while(gets(str))
166     {
167         ans=0;
168         memset(visit,0,sizeof(visit));
169         for(i=0;str[i];i++)
170             if(str[i]=='x') a[++ans]=9;
171             else if(str[i]!=' ') a[++ans]=str[i]-'0';
172             ed=0;
173         ans=check(a);
174         if(ans%2) {puts("unsolvable");continue;}
175             bfs();
176             j=0;
177             while(ed!=st)
178             {
179                 str[j++]=visit1[ed];
180                 ed=pre[ed];
181             }
182             for(i=j-1;i>=0;i--)
183                 printf("%c",str[i]);
184                 puts("");
185     }
186     return 0;
187 }

View Code