HUD 1043 Eight 八数码问题 A*算法 1667 The Rotation Game IDA*算法

HUD 1043 Eight 八数码问题 A算法 1667 The Rotation Game IDA算法

先是这周是搜索的题，网站：http://acm.hdu.edu.cn/webcontest/contest_show.php?cid=6041

主要内容是BFS,A*,IDA*，还有一道K短路的,.....木做，本来1009是说要用迭代加深做，但是我在他讲之前就用BFSA了，虽然很耗时，但还是过了，10000MS的时限，我8000+MS.......

1001 Eight 八数码问题

先把代码放上来

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

500MS

3524K

3183 B

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<queue>
  6 using namespace std;
  7 class  Node
  8 {
  9 public:
 10     int maze[3][3];   //八数码具体情况
 11     int h,g;    //两个估价函数
 12     int x,y;   //空位的位置
 13     int Hash;   //HASH值
 14     bool operator<(const Node n1)const{     //优先队列第一关键字为h,第二关键字为g
 15         return h!=n1.h?h>n1.h:g>n1.g;
 16     }
 17     bool check()     //判断是否合法
 18     {    
 19         if(x>=0&&x<3&&y>=0&&y<3)
 20             return true;
 21         return false;
 22     }
 23 }s,u,v;
 24 int HASH[9]={1,1,2,6,24,120,720,5040,40320};   //HASH的权值
 25 int des=322560;   //目标情况的HASH值
 26 int vis[400000];            //判断状态已遍历，初始为-1，否则为到达这步的转向
 27 int pre[400000];        //路径父节点
 28 int way[4][2]={{0,1},{0,-1},{1,0},{-1,0}};   //四个方向
 29 int get_hash(Node tmp)     //获得HASH值
 30 {    
 31     int a[9],k=0;
 32     for(int i=0;i<3;i++)
 33         for(int j=0;j<3;j++)
 34             a[k++]=tmp.maze[i][j];
 35     int res=0;
 36     for(int i=0;i<9;i++){
 37         int k=0;
 38         for(int j=0;j<i;j++)
 39             if(a[j]>a[i])
 40                 k++;
 41         res+=HASH[i]*k;
 42     }
 43     return res;
 44 }
 45 bool isok(Node tmp){    //求出逆序对，判断是否有解
 46     int a[9],k=0;
 47     for(int i=0;i<3;i++)
 48         for(int j=0;j<3;j++)
 49             a[k++]=tmp.maze[i][j];
 50     int sum=0;
 51     for(int i=0;i<9;i++)
 52         for(int j=i+1;j<9;j++)
 53             if(a[j]&&a[i]&&a[i]>a[j])
 54                 sum++;
 55     return !(sum&1);    //由于目标解为偶数，所以状态的逆序数为偶数才可行
 56 }
 57 int get_h(Node tmp){   //获得估价函数H
 58     int ans=0;
 59     for(int i=0;i<3;i++)
 60         for(int j=0;j<3;j++)
 61             if(tmp.maze[i][j])
 62                 ans+=abs(i-(tmp.maze[i][j]-1)/3)+abs(j-(tmp.maze[i][j]-1)%3);
 63     return ans;
 64 }
 65 void astar(){    //搜索
 66     priority_queue<Node>que;    //优先队列
 67     que.push(s);
 68     while(!que.empty())
 69     {
 70         u=que.top();
 71         que.pop();   //出队
 72         for(int i=0;i<4;i++)
 73         {
 74             v=u;
 75             v.x+=way[i][0];
 76             v.y+=way[i][1];
 77             if(v.check())
 78             {
 79                 swap(v.maze[v.x][v.y],v.maze[u.x][u.y]);   //将空位和相邻位交换
 80                 v.Hash=get_hash(v);             //得到HASH值
 81                 if(vis[v.Hash]==-1)//判断是否已遍历且是否可行
 82                 {   
 83                     vis[v.Hash]=i;           //保存方向
 84                     v.g++;;                  //代价++
 85                     pre[v.Hash]=u.Hash;     //保存v的父节点u
 86                     v.h=get_h(v);           //得到新的估价函数H
 87                     que.push(v);     //入队
 88                 }
 89                 if(v.Hash==des)
 90                     return ;
 91             }
 92         }
 93     }
 94 }
 95 void print()
 96 {
 97     string ans;
 98     char wu[4]={'r','l','d','u'};
 99     ans.clear();
100     int nxt=des;
101     while(pre[nxt]!=-1)        //从终点往起点找路径
102     {  
103         ans+=wu[vis[nxt]];
104         nxt=pre[nxt];   //上一个父节点
105     }
106     for(int i=ans.size()-1;i>=0;i--)
107         printf("%c",ans[i]);
108     printf("
");
109 }
110 int main()
111 {
112     char str[100];
113     while(gets(str)!=NULL)      
114     {
115         int k=0;
116         memset(vis,-1,sizeof(vis));
117         memset(pre,-1,sizeof(pre));
118         for(int i=0;i<3;i++)
119             for(int j=0;j<3;j++)
120                 {
121                 if((str[k]<='9'&&str[k]>='0')||str[k]=='x')
122                 {
123                     if(str[k]=='x')
124                     {
125                         s.maze[i][j]=0;
126                         s.x=i;
127                         s.y=j;
128                     }
129                     else
130                         s.maze[i][j]=str[k]-'0';
131                 }
132                 else
133                     j--;
134                 k++;
135             }
136         if(!isok(s))      //起始状态不可行
137         {   
138             printf("unsolvable
");
139             continue;
140         }
141         s.Hash=get_hash(s);
142         if(s.Hash==des)    
143         {  
144             printf("
");
145             continue;
146         }
147         vis[s.Hash]=-2;
148         s.g=0;s.h=get_h(s);
149         astar();   //A*
150         print();   //打印路径
151     }
152     return 0;
153 }

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <string.h>
  4 #include <string>
  5 #include <algorithm>
  6 #include <queue>
  7 using namespace std;
  8 class A
  9 {
 10 public:
 11     int a[3][3];
 12     int h,g;
 13     int x,y;
 14     int has;
 15     bool operator<(const A n)const{return h!=n.h?h>n.h:g>n.g;}
 16     bool check()
 17     {
 18         if (x>=0&&x<=2&&y>=0&&y<=2)
 19             return true;
 20         return false;
 21     }
 22 }s,w,r;
 23 int H[9]={1,1,2,6,24,120,720,5040,40320};
 24 int des=322560;
 25 int v[400000];
 26 int p[400000];
 27 int d[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
 28 
 29 bool ok(A c)
 30 {
 31     int q[9],k=0,i,j,sum=0;
 32     for(i=0;i<3;i++)
 33         for(j=0;j<3;j++)
 34         q[k++]=c.a[i][j];
 35     for(i=0;i<9;i++)
 36         for(j=i+1;j<9;j++)
 37         if(q[j]&&q[i]&&q[i]>q[j])
 38         sum++;
 39     return !(sum&1);
 40 }
 41 
 42 int gethas(A c)
 43 {
 44    int q[9],k=0,i,j,sum=0;
 45     for(i=0;i<3;i++)
 46         for(j=0;j<3;j++)
 47         q[k++]=c.a[i][j];
 48     for(i=0;i<9;i++)
 49     {
 50         int o=0;
 51         for(j=0;j<i;j++)
 52             if(q[j]>q[i])
 53                o++;
 54         sum+=H[i]*o;
 55     }
 56     return sum;
 57 }
 58 
 59 int geth(A c)
 60 {
 61     int sum=0,i,j;
 62     for(i=0;i<3;i++)
 63         for(j=0;j<3;j++)
 64         if(c.a[i][j])
 65           sum+=abs(i-(c.a[i][j]-1)/3)+abs(j-(c.a[i][j]-1)%3);
 66     return sum;
 67 }
 68 
 69 void astar()
 70 {
 71     int i;
 72     priority_queue<A>f;
 73     f.push(s);
 74     while(!f.empty())
 75     {
 76         w=f.top();
 77         f.pop();
 78         for(i=0;i<4;i++)
 79         {
 80             r=w;
 81             r.x+=d[i][0];
 82             r.y+=d[i][1];
 83             if(r.check())
 84             {
 85                 swap(r.a[w.x][w.y],r.a[r.x][r.y]);
 86                 r.has=gethas(r);
 87                 if(v[r.has]==-1)
 88                 {
 89                     v[r.has]=i;
 90                     r.g++;
 91                     p[r.has]=w.has;
 92                     r.h=geth(r);
 93                     f.push(r);
 94                 }
 95                 if(r.has==des)
 96                     return ;
 97             }
 98         }
 99     }
100 }
101 
102 void print()
103 {
104     string str;
105     char wu[4]={'r','l','d','u'};
106     str.clear();
107     int next=des,i;
108     while(p[next]!=-1)
109     {
110         str+=wu[v[next]];
111         next=p[next];
112     }
113     for(i=str.size()-1;i>=0;i--)
114         putchar(str[i]);
115     printf("
");
116 }
117 
118 int main()
119 {
120     char b[100];
121     int i,j,k;
122     while(gets(b)!=NULL)
123     {
124        memset(v,-1,sizeof(v));
125        memset(p,-1,sizeof(p));
126        k=0;
127        for(i=0;i<3;i++)
128             for(j=0;j<3;j++)
129             {
130                 if(b[k]=='x')
131                 {
132                     s.a[i][j]=0;
133                     s.x=i;
134                     s.y=j;
135                 }
136                 else if(b[k]>='0'&&b[k]<='9')
137                     s.a[i][j]=b[k]-'0';
138                 else
139                     j--;
140                 k++;
141             }
142 
143         if(!ok(s))
144         {
145             printf("unsolvable
");
146             continue;
147         }
148         s.has=gethas(s);
149         if(s.has==des)
150         {
151             printf("
");
152             continue;
153         }
154         v[s.has]=-2;
155         s.g=0;
156         s.h=geth(s);
157         astar();
158         print();
159     }
160 }

View Code

1006 The Rotation Game

第二题 IDA*算法，感觉比上面那个简单

题目网址：http://acm.hdu.edu.cn/showproblem.php?pid=1667

296MS

300K

1895 B

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <string.h>
 4 #include <algorithm>
 5 using namespace std;
 6 int maxx(int x,int y,int z)  {return max(max(x,y),z);}   //三个数的最大值
 7 int  a[9][8]={
 8     0,0,0,0,0,0,0,0,
 9     0,1,3,7,12,16,21,23,
10     0,2,4,9,13,18,22,24,
11     0,11,10,9,8,7,6,5,
12     0,20,19,18,17,16,15,14,
13     0,24,22,18,13,9,4,2,
14     0,23,21,16,12,7,3,1,
15     0,14,15,16,17,18,19,20,
16     0,5,6,7,8,9,10,11
17 };    //每一纵行和横行的编号
18 int re[9]={0,6,5,8,7,2,1,4,3};    //往回移对应的编号
19 int mid[9]={0,7,8,9,12,13,16,17,18};   //中间的8个数的编号
20 char lu[]="OABCDEFGH";    //路径
21 int b[28];    //现状
22 char father[300];       //记录父节点的编号
23 int dep;    //允许的深度
24 
25 int geth(int b[28])   //获得H值
26 {
27     int i,w[4];
28     memset(w,0,sizeof(w));
29     for(i=1;i<=8;i++)
30         w[b[mid[i]]]++;
31     return 8-maxx(w[1],w[2],w[3]);
32 }
33 
34 int IDA(int g)
35 {
36     int i,H,t,j;
37     if(g>=dep)
38         return 0;
39     for(i=1;i<=8;i++)
40     {
41         t=b[a[i][1]];
42         for(j=1;j<=6;j++)
43             b[a[i][j]]=b[a[i][j+1]];
44         b[a[i][7]]=t;
45         father[g]=i;    //记录父节点
46         H=geth(b);    //获得最新的H
47         if(!H)
48             return 1;
49         if(g+H<dep && IDA(g+1))    //A*剪枝
50             return 1;
51         t=b[a[re[i]][1]];     //回到上一步
52         for(j=1;j<=6;j++)
53             b[a[re[i]][j]]=b[a[re[i]][j+1]];
54         b[a[re[i]][7]]=t;
55     }
56     return 0;
57 }
58 
59 int main()
60 {
61     int i;
62     while(~scanf("%d",&b[1])&&b[1])
63     {
64         for(i=2;i<=24;i++)
65             scanf("%d",&b[i]);
66         dep=geth(b);
67         if(!dep)     //不需要移动
68         {
69             printf("No moves needed
");
70             printf("%d
",b[8]);
71             continue;
72         }
73         while(!IDA(0))
74             dep++;
75         for(i=0;i<=dep-1;i++)
76             printf("%c",lu[father[i]]);
77         printf("
%d
",b[8]);
78     }
79     return 0;
80 }