UVA10085隐式图搜索+八数码特殊节点记录优化

  1 /*八数码问题UVA10085:
  2 隐式图搜索：
  3 我觉得解决这类问题，有几点很重要：
  4 1、状态的表示（压缩状态表示可以减小空间复杂度）
  5 2、时间复杂度（状态数）的正确评估，你要保证暴力法是可以解决的。换句话说，状态很快会被填满
  6 3、编码的细心程度（废话，不过算法简单的话，对编码的要求自然就高了很多）
  7 
  8 显然，这道题的状态上限是9！=3*1e6，实际上是一道dfs求最大深度的题目
  9 */
 10 #include <stdio.h>
 11 #include <stdlib.h>
 12 #include <string.h>
 13 #include <math.h>
 14 #include <ctype.h>
 15 #include <string>
 16 #include <iostream>
 17 #include <sstream>
 18 #include <vector>
 19 #include <queue>
 20 #include <stack>
 21 #include <map>
 22 #include <list>
 23 #include <set>
 24 #include <algorithm>
 25 #define INF 1e10
 26 #define maxn 2000+10
 27 
 28 using namespace std;
 29 int vis[362880],fact[9];
 30 struct ret
 31 {
 32     int a[5][5];
 33 
 34 };
 35 struct Node{
 36     ret sta;
 37     int x,y;//记录当前空白格的位置，减少常数9的复杂度
 38     int deep;//bfs深度
 39     char step[maxn];
 40     void print()
 41     {
 42         for(int i=0;i<3;i++)
 43         {
 44             for(int j=0;j<3;j++)
 45             {
 46                 cout<<sta.a[i][j];
 47                 if (j<=1) cout<<" ";
 48             }
 49             cout<<endl;
 50         }
 51     }
 52 };
 53 void init_lookup_table()
 54 {
 55     memset(vis,0,sizeof(vis));
 56     fact[0]=1;
 57     for(int i=1;i<9;i++) fact[i]=fact[i-1]*i;
 58 }
 59 int try_to_insert(ret R)
 60 {
 61 
 62     int st[10];
 63     for(int i=0;i<3;i++)
 64     for(int j=0;j<3;j++)
 65        st[i*3+j]=R.a[i][j];
 66 //    for(int i=0;i<9;i++) cout<<st[i]<<" ";cout<<endl;
 67     int code=0;
 68     for(int i=0;i<9;i++)
 69     {
 70         int cnt=0;
 71         for(int j=i+1;j<9;j++) if (st[j]<st[i]) cnt++;
 72         code+=fact[8-i]*cnt;
 73 
 74     }
 75 //    cout<<code<<endl;
 76     if (vis[code]) return 0;
 77     return vis[code]=1;
 78 }
 79 
 80 int GetNum(ret x)//状态唯一确定数字
 81 {
 82     int ans=0;
 83     for(int i=0;i<3;i++)
 84     for(int j=0;j<3;j++)
 85     {
 86         ans+=x.a[i][j]*pow(10,(i*3+j));
 87     }
 88     return ans;
 89 }
 90 bool check(Node no,char c)
 91 {
 92     int x=no.x,y=no.y;
 93     if (c=='U') return (x-1)>=0;//一开始写成了>,OTL
 94     if (c=='D') return (x+1)<3;
 95     if (c=='L') return (y-1)>=0;
 96     if (c=='R') return (y+1)<3;
 97 
 98 }
 99 Node Move(Node no,char c)
100 {
101     int x=no.x,y=no.y;
102     if (c=='U') {swap(no.sta.a[x][y],no.sta.a[x-1][y]);no.x--;no.step[no.deep++]='U';}
103     if (c=='D') {swap(no.sta.a[x][y],no.sta.a[x+1][y]);no.x++;no.step[no.deep++]='D';}
104     if (c=='L') {swap(no.sta.a[x][y],no.sta.a[x][y-1]);no.y--;no.step[no.deep++]='L';}
105     if (c=='R') {swap(no.sta.a[x][y],no.sta.a[x][y+1]);no.y++;no.step[no.deep++]='R';}
106     return no;
107 }
108 int nextint(){int x;scanf("%d",&x);return x;}
109 void solve(int t)
110 {
111     int dpest=-1;Node ans;ret R;int sx,sy;
112 
113     init_lookup_table();
114     queue<Node>Q;
115 
116     for(int i=0;i<3;i++)
117     for(int j=0;j<3;j++){
118         R.a[i][j]=nextint();
119         if (R.a[i][j]==0) {sx=i;sy=j;}
120     }
121     Q.push((Node){R,sx,sy,0});
122 
123     while(!Q.empty())
124     {
125         Node no=Q.front();Q.pop();
126 //        no.print();
127         if (!try_to_insert(no.sta)) continue;
128 //        cout<<"<<<"<<endl;
129         if (no.deep>dpest) {dpest=no.deep;ans=no;}
130 
131         int x=no.x,y=no.y;
132         //向上
133         if (check(no,'U'))
134             {Node newn=Move(no,'U');Q.push(newn);}
135         if (check(no,'D'))
136             {Node newn=Move(no,'D');Q.push(newn);}
137         if (check(no,'L'))
138             {Node newn=Move(no,'L');Q.push(newn);}
139         if (check(no,'R'))
140             {Node newn=Move(no,'R');Q.push(newn);}
141     }
142     printf("Puzzle #%d
",t);
143     ans.print();
144     ans.step[ans.deep]='';
145     printf("%s
",ans.step);
146     cout<<endl;
147     return ;
148 }
149 int t;
150 int main()
151 {
152     cin>>t;
153     for(int i=1;i<=t;i++)
154     solve(i);
155 
156     return 0;
157 }