hdu 1043 Eight 经典八数码问题

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1043

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.
 
题意描述：给出一个3×3的矩阵（包含1～8数字和一个字母x），经过一些移动格子上的数后得到连续的1～8，最后一格是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 }
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/huangxf/p/4369089.html