Eight hdu 1043 八数码问题双搜

Eight

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

  1 #include <iostream>
  2 #include <string.h>
  3 #include <stdio.h>
  4 #include <math.h>
  5 #include <stdlib.h>
  6 #include <queue>
  7 using namespace std;
  8 typedef struct eight
  9 {
 10     char a[3][3];
 11     int statu,nowx,nowy;
 12 } eight;
 13 eight s,e;
 14 int f[12],flag[500000],ok;
 15 int father1[500000],father2[500000];
 16 int move1[500000],move2[500000],last;
 17 queue<eight>q1,q2;
 18 void init()
 19 {
 20     f[0]=1;
 21     int i;
 22     for(i=1; i<12; i++)f[i]=f[i-1]*i;
 23 }
 24 void work(eight &a)
 25 {
 26     int i,j,k=0,ans=0,t;
 27     char b[9];
 28     for(i=0; i<3; i++)
 29     {
 30         for(j=0; j<3; j++)
 31         {
 32             if(a.a[i][j]=='x')a.nowx=i,a.nowy=j;
 33             b[k++]=a.a[i][j];
 34         }
 35     }
 36     k=8;
 37     for(i=0; i<9; i++)
 38     {
 39         t=0;
 40         for(j=i+1; j<9; j++)
 41             if(b[j]<b[i])t++;
 42         ans+=f[k--]*t;
 43     }
 44     a.statu=ans;
 45 }
 46 void copy(eight &a,eight &b)
 47 {
 48     int i,j;
 49     for(i=0; i<3; i++)
 50         for(j=0; j<3; j++)a.a[i][j]=b.a[i][j];
 51 }
 52 int w[4][2]= {{0,1},{0,-1},{1,0},{-1,0}};
 53 void ex_BFS(eight &now,int n,int check)
 54 {
 55     int i,r,c;
 56     eight in;
 57     for(i=0; i<4; i++)
 58     {
 59 
 60         r=now.nowx+w[i][0];
 61         c=now.nowy+w[i][1];
 62         if(r>=0&&r<3&&c>=0&&c<3)
 63         {
 64             copy(in,now);
 65             swap(in.a[r][c],in.a[now.nowx][now.nowy]);
 66             work(in);
 67             if(flag[in.statu]!=n)
 68             {
 69                 if(n==1)
 70                 {
 71                     q1.push(in);
 72                     father1[in.statu]=now.statu;
 73                     move1[in.statu]=i;
 74                 }
 75                 else
 76                 {
 77                     q2.push(in);
 78                     father2[in.statu]=now.statu;
 79                     move2[in.statu]=i;
 80                 }
 81                 if(flag[in.statu]==check)
 82                 {
 83                     ok=1;
 84                     last=in.statu;
 85                     return ;
 86                 }
 87                 flag[in.statu]=n;
 88             }
 89         }
 90     }
 91 }
 92 bool TBFS(eight &s,eight &e)
 93 {
 94     memset(flag,0,sizeof(flag));
 95     memset(move1,-1,sizeof(move1));
 96     memset(move2,-1,sizeof(move2));
 97     memset(father1,-1,sizeof(father1));
 98     memset(father2,-1,sizeof(father2));
 99     eight now;
100     ok=0;
101     while(!q1.empty())q1.pop();
102     while(!q2.empty())q2.pop();
103     q1.push(s),flag[s.statu]=1;
104     q2.push(e),flag[e.statu]=2;
105     while((!q1.empty())||(!q2.empty()))
106     {
107         now=q1.front();
108         q1.pop();
109         ex_BFS(now,1,2);
110         if(ok)return 1;
111 
112         now=q2.front();
113         q2.pop();
114         ex_BFS(now,2,1);
115         if(ok)return 1;
116     }
117     return 0;
118 }
119 bool check1(eight &s)
120 {
121     int i,j,k=0;
122     char b[9];
123     for(i=0; i<3; i++)
124         for(j=0; j<3; j++)
125             b[k++]=s.a[i][j];
126     int ans=0;
127     for(i=0; i<9; i++)
128     {
129         if(b[i]!='x')
130             for(j=0; j<i; j++)
131                 if(b[j]!='x'&&b[i]<b[j])ans++;
132     }
133     return (ans&1);
134 }
135 void printpath()
136 {
137     deque<char>q;
138     while(!q.empty())q.pop_back();
139     int now=last;
140     while(father1[now]!=-1)
141     {
142         if(move1[now]==0)q.push_back('r');
143         else if(move1[now]==1)q.push_back('l');
144         else if(move1[now]==2)q.push_back('d');
145         else if(move1[now]==3)q.push_back('u');
146         now=father1[now];
147     }
148     while(!q.empty())
149     {
150         cout<<q.back();
151         q.pop_back();
152     }
153 
154     now=last;
155     while(father2[now]!=-1)
156     {
157         if(move2[now]==0)cout<<'l';
158         else if(move2[now]==1)cout<<'r';
159         else if(move2[now]==2)cout<<'u';
160         else if(move2[now]==3)cout<<'d';
161         now=father2[now];
162     }
163 }
164 int main()
165 {
166     int i,j;
167     init();
168     char w;
169     while(cin>>w)
170     {
171         char an='1';
172         for(i=0; i<3; i++)
173             for(j=0; j<3; j++)
174             {
175                 if(i||j)
176                 cin>>s.a[i][j];
177                 e.a[i][j]=an++;
178             }
179             s.a[0][0]=w;
180 
181         e.a[2][2]='x';
182         if(check1(s))
183         {
184             cout<<"unsolvable"<<endl;
185             continue;
186         }
187         work(s);
188         work(e);
189         if(s.statu==e.statu)
190         {
191             cout<<endl;
192             continue;
193         }
194         if(TBFS(s,e))
195         {
196             printpath();
197             cout<<endl;
198         }
199         else
200             cout<<"unsolvable"<<endl;
201     }
202 
203 }

View Code

Eight hdu 1043 八数码问题 双搜

Eight

Eight hdu 1043 八数码问题双搜