hdu 1043 Eight経典八数コード問題
33051 ワード
テーマリンク：http://acm.hdu.edu.cn/showproblem.php?pid=1043
The 15-puzle 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 sland tile s，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 cal the missing。the object of the puzle is to arrange the tiles so that the y ardersed as:
Not all puzles can be soloved;n 1870,a man named Sam Loyd was famous for distributing an unsoluble version of the puzle，and
fustringmany people.In fact，all you have to to make a reglar puzle into an soluble one is to swap two tiles.
In this proble、you will write a program for soling the less well-known 8-puzle、compsed of tiles on a three by three
arrangement.
一つの3を与える。×3の行列（1～8の数字と1文字xを含む）は、いくつかの移動格子上の数を経て連続する1～8を得て、最後の1マスはxで、最小移動ステップ数を求めます。
アルゴリズム解析：古典的な八数コード問題。八数コードは検索の問題です。古典的な解法はbfs、A＊、IDA＊などがあります。インターネットの資料が多いので、ここで簡単にA*を紹介します。
A*:f=g+h関数です。gは始点から現在点までの移動ステップ数を表し、hは現在点から目標点までの最小移動ステップ数の予測を表します。出発点と目標点を除いて、私達は任意の点を歩く時、次のステップはfより小さい継続を選ぶべきだと考えられます。（hの計算についてはマンハッタン距離の公式を使うことができます。）
カント展開：この問題の中の役割はhash関数を実施することにあります。現在のこのステップの後に新しい行列が得られます。カント展開式でこのマトリックスのhash値を計算して、幅検索で判断します。
もう一つの最適化点があります。現在の行列が目標行列に達するかどうかを判断します。（マトリックスの中の二つの数を交換した後、逆の順序のパリティと目標行列が一致してこそ、目標行列に到達する機会があります。）
The 15-puzle 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 sland tile s，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 cal the missing。the object of the puzle is to arrange the tiles so that the y ardersed as:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 x
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->Not all puzles can be soloved;n 1870,a man named Sam Loyd was famous for distributing an unsoluble version of the puzle，and
fustringmany people.In fact，all you have to to make a reglar puzle into an soluble one is to swap two tiles.
In this proble、you will write a program for soling the less well-known 8-puzle、compsed of tiles on a three by three
arrangement.
一つの3を与える。×3の行列（1～8の数字と1文字xを含む）は、いくつかの移動格子上の数を経て連続する1～8を得て、最後の1マスはxで、最小移動ステップ数を求めます。
アルゴリズム解析：古典的な八数コード問題。八数コードは検索の問題です。古典的な解法はbfs、A＊、IDA＊などがあります。インターネットの資料が多いので、ここで簡単にA*を紹介します。
A*:f=g+h関数です。gは始点から現在点までの移動ステップ数を表し、hは現在点から目標点までの最小移動ステップ数の予測を表します。出発点と目標点を除いて、私達は任意の点を歩く時、次のステップはfより小さい継続を選ぶべきだと考えられます。（hの計算についてはマンハッタン距離の公式を使うことができます。）
カント展開：この問題の中の役割はhash関数を実施することにあります。現在のこのステップの後に新しい行列が得られます。カント展開式でこのマトリックスのhash値を計算して、幅検索で判断します。
もう一つの最適化点があります。現在の行列が目標行列に達するかどうかを判断します。（マトリックスの中の二つの数を交換した後、逆の順序のパリティと目標行列が一致してこそ、目標行列に到達する機会があります。）
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cstdlib>
5 #include<cmath>
6 #include<algorithm>
7 #include<queue>
8 #include<vector>
9 #define inf 0x7fffffff
10 using namespace std;
11 const int maxn=10;
12 const int M = 400000+10;
13
14 struct node
15 {
16 int mase[3][3];
17 int x,y;
18 int f,g,h;
19 int flag;
20 friend bool operator < (node a,node b)
21 {
22 return a.f > b.f;
23 }
24 }start,tail;
25 int pre[M],v[M];
26
27 char str[4]={'u','d','l','r' };
28 int Can[10]={1,1,2,6,24,120,720,5040,40320 };
29 const int destination=46234;
30 int Cantor(node cur) ///
31 {
32 int an[10],k=0;
33 for (int i=0 ;i<3 ;i++)
34 for (int j=0 ;j<3 ;j++)
35 an[k++]=cur.mase[i][j];
36 int sum=0;
37 for (int i=0 ;i<9 ;i++)
38 {
39 int k=0;
40 for (int j=i+1 ;j<9 ;j++)
41 if (an[i]>an[j]) k++;
42 sum += k*Can[9-i-1];
43 }
44 return sum+1;
45 }
46
47 int is_ok(node an) ///
48 {
49 int a[10],k=0;
50 for (int i=0 ;i<3 ;i++)
51 for (int j=0 ;j<3 ;j++)
52 a[k++]=an.mase[i][j];
53 int sum=0;
54 for (int i=0 ;i<k ;i++) if (a[i]!=0)
55 for (int j=0 ;j<i ;j++)
56 if (a[j]!=0 && a[j]>a[i]) sum ++ ;
57 if (sum&1) return 0;
58 return 1;
59 }
60
61 void print(node cur)
62 {
63 string ans;
64 int sum=destination;
65 while (pre[sum] != -1)
66 {
67 switch (v[sum]) {
68 case 0 : ans += str[0];break;
69 case 1 : ans += str[1];break;
70 case 2 : ans += str[2];break;
71 case 3 : ans += str[3];break;
72 }
73 sum=pre[sum];
74 }
75 int len=ans.size() ;
76 for (int i=len-1 ;i>=0 ;i--) putchar(ans[i]);
77 return ;
78 }
79
80 pair<int,int> pii[10];
81 int getH(node cur)
82 {
83 int r=0,c=0;
84 for (int i=1 ;i<=9 ;i++)
85 {
86 pii[i%9].first=r ;
87 pii[i%9].second=c;
88 c++;
89 if (c==3) {r++;c=0; }
90 }
91 int sum=0;
92 for (int i=0 ;i<3 ;i++)
93 {
94 for (int j=0 ;j<3 ;j++)
95 {
96 int u=cur.mase[i][j];
97 sum += abs(pii[u].first-i)+abs(pii[u].second-j);
98 }
99 }
100 return sum;
101 }
102
103 int vis[M];
104 int an[4][2]={-1,0, 1,0, 0,-1, 0,1 };
105 void A_star(node cur)
106 {
107 priority_queue<node> Q;
108 cur.g=0 ;cur.h=getH(cur);
109 cur.f=cur.g + cur.h ;
110 cur.flag=-1;
111 Q.push(cur);
112 memset(vis,-1,sizeof(vis));
113 memset(pre,-1,sizeof(pre));
114 memset(v,-1,sizeof(v));
115 vis[Cantor(cur) ]=1;
116 while (!Q.empty())
117 {
118 cur=Q.top() ;Q.pop() ;
119 if (Cantor(cur)==destination)
120 {
121 // cout<<cur.g<<endl;
122 // for (int i=0 ;i<3 ;i++)
123 // {
124 // for (int j=0 ;j<3 ;j++)
125 // cout<<cur.mase[i][j]<<" ";
126 // cout<<endl;
127 // }
128 ///
129 print(cur);
130 return ;
131 }
132 for (int i=0 ;i<4 ;i++)
133 {
134 tail.x=cur.x+an[i][0];
135 tail.y=cur.y+an[i][1];
136 int x=cur.x ,y=cur.y ;
137 for (int u=0 ;u<3 ;u++)
138 for (int v=0 ;v<3 ;v++)
139 tail.mase[u][v]=cur.mase[u][v];
140 if (tail.x<0||tail.x>=3||tail.y<0||tail.y>=3) continue;
141 swap(tail.mase[tail.x][tail.y],tail.mase[x][y]);
142 int sum=Cantor(tail);
143 if (vis[sum]==-1)
144 {
145 if (is_ok(tail)==0) continue;
146 vis[sum]=1;
147 tail.g=cur.g+1;
148 tail.h=getH(tail);
149 tail.f=tail.g+tail.h;
150 if (tail.x==x+1) tail.flag=1;
151 else if (tail.x==x-1) tail.flag=0;
152 else if (tail.y==y-1) tail.flag=2;
153 else if (tail.y==y+1) tail.flag=3;
154 pre[sum]=Cantor(cur);
155 v[sum]=i;
156 Q.push(tail);
157 }
158 }
159 }
160 return ;
161 }
162
163 int main()
164 {
165 char str[100];
166 while (gets(str))
167 {
168 int r=0,c=0;
169 int len=strlen(str);
170 int ok=0;
171 for (int i=0 ;i<len ;i++)
172 {
173 if (str[i]>='0' && str[i]<='9')
174 {
175 start.mase[r][c]=str[i]-'0';
176 c++;
177 if (c==3) {r++;c=0; }
178 }
179 else if (str[i]=='x')
180 {
181 start.mase[r][c]=0;
182 start.x=r ;start.y=c ;
183 c++;
184 if (c==3) {r++;c=0; }
185 }
186 }
187 int sum=Cantor(start);
188 if (sum==destination) {printf("
");continue; }
189 if (is_ok(start)==0) {printf("unsolvable
");continue; }
190 A_star(start);
191 printf("
");
192 }
193 return 0;
194 }