去年听ReDow讲A*,IDA*，当时小菜（现在也是），就没把那些东西列在学习范围内，前些天LCY让我讲搜索进阶，就做了几题，分享下做题感受～～
HDU 1043 Eight 涉及到人生完不完整的一道题，有位大神总结出了八数码的8重境界，可见其经典程度无出其右～～
A*: 因为每次移动都会影响一个点的曼哈顿距离（不算x），构造h()为所有数字块的曼哈顿距离和，用逆序数hash（算x），根据逆序数奇偶性（不算x）减掉无法到达的情况，A*跑了656ms，POJ 16ms
View Code 1 #include
2 #include 3 #include 4 using namespace std; 5 6 struct S{ 7 char maze[3][3]; 8 int x,y; 9 int g,h,f; 10 S(){} 11 S(const S& ts){ 12 for(int i=0;i<3;i++){ 13 for(int j=0;j<3;j++){ 14 maze[i][j]=ts.maze[i][j]; 15 } 16 } 17 x=ts.x; y=ts.y; 18 g=ts.g; h=ts.h; f=ts.f; 19 } 20 friend bool operator< (const S& a,const S& b){ 21 return a.f>b.f; 22 } 23 }s; 24 const int fac[]={1,1,2,6,24,120,720,5040,40320}; 25 bool vis[363000]; 26 int pre[363000]; 27 char op[363000]; 28 29 inline int inv_hash(S ts){ 30 char str[10]; int ans=0; 31 for(int i=0;i<3;i++){ 32 for(int j=0;j<3;j++){ 33 str[i*3+j]=ts.maze[i][j]; 34 int cnt=0; 35 for(int k=i*3+j-1;k>=0;k--){ 36 if(str[k]>str[i*3+j]) cnt++; 37 } 38 ans+=fac[i*3+j]*cnt; 39 } 40 } 41 return ans; 42 } 43 44 const int pos[][2]={{0,0},{0,1},{0,2},{1,0},{1,1},{1,2},{2,0},{2,1},{2,2}}; 45 inline int ABS(int x){return x<0?-x:x;} 46 inline int h(S ts){ 47 int val=0; 48 for(int i=0;i<3;i++){ 49 for(int j=0;j<3;j++){ 50 if(ts.maze[i][j]=='x') continue; 51 int c=ts.maze[i][j]-'1'; 52 val+=ABS(pos[c][0]-i)+ABS(pos[c][1]-j); 53 } 54 } 55 return val; 56 } 57 58 const int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; 59 bool bfs(){ 60 memset(vis,false,sizeof(vis)); 61 62 priority_queue que; 63 que.push(s); 64 while(!que.empty()){ 65 S u=que.top(); que.pop(); 66 int ihu=inv_hash(u); 67 68 for(int i=0;i<4;i++){ 69 S v=u; 70 v.x+=dir[i][0]; 71 v.y+=dir[i][1]; 72 if(v.x<0||v.y<0||v.x>=3||v.y>=3) continue; 73 v.maze[u.x][u.y]=u.maze[v.x][v.y]; 74 v.maze[v.x][v.y]='x'; 75 v.g+=1; v.h=h(v); v.f=v.g+v.h; 76 int ihv=inv_hash(v); 77 if(vis[ihv]) continue; 78 vis[ihv]=true; 79 pre[ihv]=ihu; 80 if(i==0) op[ihv]='d'; 81 else if(i==1) op[ihv]='r'; 82 else if(i==2) op[ihv]='u'; 83 else if(i==3) op[ihv]='l'; 84 if(ihv==0) return true; 85 que.push(v); 86 } 87 } 88 return false; 89 } 90 91 inline bool inv_check(){ 92 char str[10]; 93 int cnt=0; 94 for(int i=0;i<3;i++){ 95 for(int j=0;j<3;j++){ 96 str[i*3+j]=s.maze[i][j]; 97 if(str[i*3+j]=='x') continue; 98 for(int k=i*3+j-1;k>=0;k--){ 99 if(str[k]=='x') continue;
100 if(str[k]>str[i*3+j]) cnt++;
101 }
102 }
103 }
104 return !(cnt&1);
105 }
106 107 char in[100];
108 char stk[100];
109 int main(){
110 while(gets(in)){
111 for(int i=0,x=0,y=0;in[i];i++){
112 if((in[i]<='9'&&in[i]>='0')||in[i]=='x'){
113 s.maze[x][y]=in[i];
114 if(in[i]=='x'){s.x=x;s.y=y;}
115 y++; if(y==3) y=0,x++;
116 }
117 }
118 119 if(!inv_check()){
120 puts("unsolvable");
121 continue;
122 }
123 s.g=0; s.h=h(s); s.f=s.h;
124 125 int shash=inv_hash(s);
126 if(shash==0){puts(""); continue;}
127 bfs();
128 int top=-1,thash=0;
129 while(thash!=shash){
130 stk[++top]=op[thash];
131 thash=pre[thash];
132 }
133 for(int i=top;i>=0;i--){
134 putchar(stk[i]);
135 }
136 puts("");
137 }
138 }
单广预处理: 从最终状态向所有状态搜索，记录前驱，然后直接输出就好了，HDOJ 93ms POJ 313ms
View Code 1 #include 2 #include 3 #include 4 using namespace std; 5 6 struct S{ 7 char maze[3][3]; 8 int x,y; 9 10 S(){}
11 S(const char *str){
12 for(int i=0,tx=0,ty=0;str[i];i++){
13 if((str[i]<='9'&&str[i]>='0')||str[i]=='x'){
14 maze[tx][ty]=str[i];
15 if(str[i]=='x'){x=tx;y=ty;}
16 ty++;if(ty==3){ty=0;tx++;}
17 }
18 }
19 }
20 };
21 int pre[363000];
22 char op[363000];
23 24 const int fac[]={1,1,2,6,24,120,720,5040,40320};
25 bool vis[363000];
26 inline int inv_hash(S ts){
27 char str[10]; int ans=0;
28 for(int i=0;i<3;i++){
29 for(int j=0;j<3;j++){
30 str[i*3+j]=ts.maze[i][j];
31 int cnt=0;
32 for(int k=i*3+j-1;k>=0;k--){
33 if(str[k]>str[i*3+j]) cnt++;
34 }
35 ans+=fac[i*3+j]*cnt;
36 }
37 }
38 return ans;
39 }
40 41 S s;
42 const int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
43 const char cdir[]="dulr";
44 void bfs(){
45 memset(vis,false,sizeof(vis));
46 memset(pre,-1,sizeof(pre));
47 48 queue que;
49 que.push(s);
50 while(!que.empty()){
51 S u=que.front(); que.pop();
52 int ihu=inv_hash(u);
53 for(int i=0;i<4;i++){
54 S v=u;
55 v.x+=dir[i][0];
56 v.y+=dir[i][1];
57 if(v.x<0||v.y<0||v.x>=3||v.y>=3) continue;
58 v.maze[u.x][u.y]=v.maze[v.x][v.y];
59 v.maze[v.x][v.y]='x';
60 int ihv=inv_hash(v);
61 if(vis[ihv]) continue;
62 vis[ihv]=true;
63 pre[ihv]=ihu;
64 op[ihv]=cdir[i];
65 que.push(v);
66 }
67 }
68 }
69 70 char in[100];
71 char stk[100];
72 int main(){
73 s=S("12345678x");
74 bfs();
75 76 while(gets(in)){
77 s=S(in);
78 int ihs=inv_hash(s);
79 if(pre[ihs]==-1){puts("unsolvable");continue;}
80 if(ihs==0){puts("");continue;}
81 int top=-1,tmp=ihs;
82 while(tmp){
83 putchar(op[tmp]);
84 tmp=pre[tmp];
85 }
86 puts("");
87 }
88 }
IDA*: 和A*相同的h()函数，跑了1s+，POJ 63ms，500k的内存是其优势
View Code 1 #include 2 #include 3 using namespace std; 4 5 struct S{ 6 char maze[3][3]; 7 int x,y; 8 int g,h,f; 9 S(){} 10 S(const S& ts){ 11 for(int i=0;i<3;i++){ 12 for(int j=0;j<3;j++){ 13 maze[i][j]=ts.maze[i][j]; 14 } 15 } 16 x=ts.x; y=ts.y; 17 } 18 19 void show(){ 20 for(int i=0;i<3;i++){ 21 for(int j=0;j<3;j++){ 22 putchar(maze[i][j]); 23 }puts(""); 24 } 25 } 26 }; 27 28 const int pos[][2]={{0,0},{0,1},{0,2},{1,0},{1,1},{1,2},{2,0},{2,1},{2,2}}; 29 inline int ABS(int x){ 30 if(x<0) return -x; 31 else return x; 32 } 33 inline int h(S ts){ 34 int val=0; 35 for(int i=0;i<3;i++){ 36 for(int j=0;j<3;j++){ 37 if(ts.maze[i][j]=='x') continue; 38 int c=ts.maze[i][j]-'1'; 39 val+=ABS(pos[c][0]-i)+ABS(pos[c][1]-j); 40 } 41 } 42 return val; 43 } 44 45 int fac[]={1,1,2,6,24,120,720,5040,40320}; 46 inline int inv_hash(S ts){ 47 char str[10]; int ans=0; 48 for(int i=0;i<3;i++){ 49 for(int j=0;j<3;j++){ 50 str[i*3+j]=ts.maze[i][j]; 51 int cnt=0; 52 for(int k=i*3+j-1;k>=0;k--){ 53 if(str[k]>str[i*3+j]) cnt++; 54 } 55 ans+=fac[i*3+j]*cnt; 56 } 57 } 58 return ans; 59 } 60 61 int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; 62 int ans[50],deep; 63 bool vis[363000]; 64 S ts; 65 bool dfs(int d){ 66 if(h(ts)==0) return true; 67 if(h(ts)+d>deep) return false; 68 69 int x=ts.x; 70 int y=ts.y; 71 for(int i=0;i<4;i++){ 72 int tx=ts.x+dir[i][0]; 73 int ty=ts.y+dir[i][1]; 74 if(tx<0||ty<0||tx>=3||ty>=3) continue; 75 ts.maze[x][y]=ts.maze[tx][ty]; 76 ts.maze[tx][ty]='x'; 77 int tmp=inv_hash(ts); 78 if(vis[tmp]){ 79 ts.maze[tx][ty]=ts.maze[x][y]; 80 ts.maze[x][y]='x'; 81 continue; 82 } 83 vis[tmp]=true; 84 ts.x=tx; ts.y=ty; 85 ans[d]=i; 86 if(dfs(d+1)) return true; 87 vis[tmp]=false; 88 ts.x=x; ts.y=y; 89 ts.maze[tx][ty]=ts.maze[x][y]; 90 ts.maze[x][y]='x'; 91 } 92 return false; 93 } 94 95 S s; 96 bool inv_check(){ 97 char str[10]; 98 int cnt=0; 99 for(int i=0;i<3;i++){
100 for(int j=0;j<3;j++){
101 str[i*3+j]=s.maze[i][j];
102 if(str[i*3+j]=='x') continue;
103 for(int k=i*3+j-1;k>=0;k--){
104 if(str[k]=='x') continue;
105 if(str[k]>str[i*3+j]) cnt++;
106 }
107 }
108 }
109 return !(cnt&1);
110 }
111 112 113 char in[100];
114 int main(){
115 while(gets(in)){
116 for(int i=0,x=0,y=0;in[i];i++){
117 if((in[i]<='9'&&in[i]>='0')||in[i]=='x'){
118 s.maze[x][y]=in[i];
119 if(in[i]=='x'){s.x=x;s.y=y;}
120 y++;
121 if(y==3) y=0,x++;
122 }
123 }
124 if(!inv_check()){ puts("unsolvable"); continue;}
125 memset(vis,false,sizeof(vis));
126 vis[inv_hash(s)]=true;
127 ts=s; deep=0;
128 while(true){
129 if(dfs(0)) break;
130 deep++;
131 }
132 for(int i=0;i
HDU 1667 The Rotation Game
IDA*的入门题目，状态过多容易超内存，正好体现了IDA*的优势，每次操作移动能使一个数字进入中间的八个位置，所以构造h()=8-max(1,2,3在中间8个位置的个数)，自己的写的太挫了，跑了1s多，后来问ReDow大神要了代码，171ms
View Code 1 #include 2 #include 3 using namespace std; 4 5 int maze[10][10]={0}; 6 bool check(){ 7 if(maze[3][3]!=maze[3][4]) return false; 8 if(maze[3][3]!=maze[3][5]) return false; 9 if(maze[3][3]!=maze[4][3]) return false; 10 if(maze[3][3]!=maze[5][3]) return false; 11 if(maze[3][3]!=maze[5][4]) return false; 12 if(maze[3][3]!=maze[5][5]) return false; 13 if(maze[3][3]!=maze[4][5]) return false; 14 return true; 15 } 16 17 void roA(){ 18 int tmp=maze[1][3]; 19 for(int i=1;i<=6;i++) maze[i][3]=maze[i+1][3]; 20 maze[7][3]=tmp; 21 } 22 23 void roB(){ 24 int tmp=maze[1][5]; 25 for(int i=1;i<=6;i++) maze[i][5]=maze[i+1][5]; 26 maze[7][5]=tmp; 27 } 28 29 void roC(){ 30 int tmp=maze[3][7]; 31 for(int i=7;i>=2;i--) maze[3][i]=maze[3][i-1]; 32 maze[3][1]=tmp; 33 } 34 35 void roD(){ 36 int tmp=maze[5][7]; 37 for(int i=7;i>=2;i--) maze[5][i]=maze[5][i-1]; 38 maze[5][1]=tmp; 39 } 40 41 void roE(){ 42 int tmp=maze[7][5]; 43 for(int i=7;i>=2;i--) maze[i][5]=maze[i-1][5]; 44 maze[1][5]=tmp; 45 } 46 47 void roF(){ 48 int tmp=maze[7][3]; 49 for(int i=7;i>=2;i--) maze[i][3]=maze[i-1][3]; 50 maze[1][3]=tmp; 51 } 52 53 void roG(){ 54 int tmp=maze[5][1]; 55 for(int i=1;i<=6;i++) maze[5][i]=maze[5][i+1]; 56 maze[5][7]=tmp; 57 } 58 59 void roH(){ 60 int tmp=maze[3][1]; 61 for(int i=1;i<=6;i++) maze[3][i]=maze[3][i+1]; 62 maze[3][7]=tmp; 63 } 64 65 66 int h(){ 67 int a[4]={0}; 68 for(int i=3;i<=5;i++){ 69 a[maze[3][i]]++; 70 a[maze[5][i]]++; 71 } 72 a[maze[4][3]]++; 73 a[maze[4][5]]++; 74 75 int max=0; 76 for(int i=1;i<=3;i++){ 77 if(maxdeep) return false; 87 roA(); 88 ans[d]='A'; 89 if(dfs(d+1)) return true; 90 roF(); 91 92 roB(); 93 ans[d]='B'; 94 if(dfs(d+1)) return true; 95 roE(); 96 97 roC(); 98 ans[d]='C'; 99 if(dfs(d+1)) return true;
100 roH();
101 102 roD();
103 ans[d]='D';
104 if(dfs(d+1)) return true;
105 roG();
106 107 roE();
108 ans[d]='E';
109 if(dfs(d+1)) return true;
110 roB();
111 112 roF();
113 ans[d]='F';
114 if(dfs(d+1)) return true;
115 roA();
116 117 roG();
118 ans[d]='G';
119 if(dfs(d+1)) return true;
120 roD();
121 122 roH();
123 ans[d]='H';
124 if(dfs(d+1)) return true;
125 roC();
126 return false;
127 }
128 129 int main(){
130 for(int i=1;i<=7;i++) maze[3][i]=maze[5][i]=1;
131 for(int i=1;i<=7;i++) maze[i][3]=maze[i][5]=1;
132 while(true){
133 for(int i=1;i<=7;i++){
134 for(int j=1;j<=7;j++){
135 if(maze[i][j]==0) continue;
136 scanf("%d",&maze[i][j]);
137 if(maze[i][j]==0) return 0;
138 }
139 }
140 if(check()){
141 puts("No moves needed");
142 printf("%d\n",maze[3][3]);
143 continue;
144 }
145 deep=1;
146 while(true){
147 if(dfs(0)) break;
148 deep++;
149 }
150 151 for(int i=0;i
HDU 2234 无题I
IDA*，开始写挫了，加了A*还是超时，又乱搞了好久才过，后来重写了一遍，2s+；每次移动改变四个点的曼哈顿距离，即h()=(曼哈顿距离和+3)/4 )；看到CY 1.3s 求代码得知是普通的dfs，数据水了...
View Code 1 #include 2 #include 3 using namespace std; 4 5 char maze[5][5]; 6 inline void roL(int x){ 7 char t=maze[x][0]; 8 maze[x][0]=maze[x][1]; 9 maze[x][1]=maze[x][2]; 10 maze[x][2]=maze[x][3]; 11 maze[x][3]=t; 12 } 13 inline void roR(int x){ 14 char t=maze[x][3]; 15 maze[x][3]=maze[x][2]; 16 maze[x][2]=maze[x][1]; 17 maze[x][1]=maze[x][0]; 18 maze[x][0]=t; 19 } 20 inline void roU(int x){ 21 char t=maze[0][x]; 22 maze[0][x]=maze[1][x]; 23 maze[1][x]=maze[2][x]; 24 maze[2][x]=maze[3][x]; 25 maze[3][x]=t; 26 } 27 inline void roD(int x){ 28 int t=maze[3][x]; 29 maze[3][x]=maze[2][x]; 30 maze[2][x]=maze[1][x]; 31 maze[1][x]=maze[0][x]; 32 maze[0][x]=t; 33 } 34 35 bool flag[5]; 36 inline int h(){ 37 int val=20; 38 int tmp=0; 39 for(int i=0;i<4;i++){ 40 int cnt=4; 41 memset(flag,false,sizeof(flag)); 42 for(int j=0;j<4;j++){ 43 if(flag[maze[i][j]-'1']) continue; 44 flag[maze[i][j]-'1']=true; 45 cnt--; 46 } 47 tmp+=3-cnt; 48 } 49 if(tmpdeep) return false; 69 70 for(int i=0;i<4;i++){ 71 72 roL(i); 73 if(dfs(d+1)) return true; 74 roR(i); 75 76 roR(i); 77 if(dfs(d+1)) return true; 78 roL(i); 79 80 roU(i); 81 if(dfs(d+1)) return true; 82 roD(i); 83 84 roD(i); 85 if(dfs(d+1)) return true; 86 roU(i); 87 } 88 return false; 89 } 90 91 inline void in(char& c){ 92 c=getchar(); 93 while(c<=32) c=getchar(); 94 } 95 96 int main(){ 97 int t; 98 scanf("%d",&t); 99 while(t--){
100 for(int i=0;i<4;i++){
101 for(int j=0;j<4;j++){
102 in(maze[i][j]);
103 }
104 }
105 deep=0;
106 while(deep<=5){
107 if(dfs(0)) break;
108 deep++;
109 }
110 if(deep<=5) printf("%d\n",deep);
111 else puts("-1");
112 }
113 }
HDU 1560 DNA sequence
IDA*: 容易看出最少步数肯定是大于等于最大字符长度的，所以就构造 h() 为所有剩余长度的最大值，2s
View Code 1 #include 2 #include 3 #include 4 using namespace std; 5 #define MAX(a,b) (a>b?a:b) 6 7 char code[]="ATGC"; 8 int pos[10],n; 9 int h(){
10 int ans=0;
11 for(int i=0;ideep) return false;
23 for(int i=0;i<4;i++){
24 bool flag=false;
25 int tpos[10];
26 for(int j=0;j
单广: 去年写了一个很挫很挫的单广，在各种TLE，MLE，RE之后终于4984ms过掉了(限5s)，今年吓怕了不敢写，后来向hh要了他的125ms的代码，单广，就模仿hh的代码，很装逼的用8进制压缩，结果状态由300w骤升至1500w，还要用bitset来hash，跑400+ms，就不拿出来丢人了；hh的代码直接开int进行hash，每组cas的hash值不同，这样就省去了每次初始化的消耗，hh的代码～
View Code 1 #include "stdio.h" 2 #include "string" 3 #define M 1679616+100000 4 struct H{ 5 int st; 6 int len; 7 }q[M]; 8 int hash[M],cas = 1; 9 int n , end ,len;
10 char str[8][8];
11 char ku[] = "ACGT";
12 int bfs() {
13 int head,tail,i,st;
14 int pos[8];
15 q[0].len = 0;
16 q[0].st = 0;
17 head = tail = 0;
18 while(head <= tail) {
19 st = q[head].st;
20 for(i = 0 ; i < n ; i ++) {
21 pos[i] = st%len;
22 st/=len;
23 }
24 for(int j = 0 ; j < 4 ; j ++) {
25 st = 0;
26 for(i = n-1; i >= 0 ;i --) {
27 st = st * len + pos[i] + (str[i][pos[i]] == ku[j]);
28 }
29 if(hash[st] == cas) {
30 continue;
31 }
32 if(st == end) {
33 return q[head].len + 1;
34 }
35 hash[st] = cas;
36 tail ++;
37 q[tail].len = q[head].len + 1;
38 q[tail].st = st;
39 }
40 head ++;
41 }
42 return -1;
43 }
44 int main() {
45 int T , i ;
46 scanf("%d",&T);
47 while(T --) {
48 scanf("%d",&n);
49 len = 0;
50 for(i = 0 ; i < n ; i ++) {
51 scanf("%s",str[i]);
52 if(strlen(str[i]) > len) {
53 len = strlen(str[i]);
54 }
55 }
56 len ++;
57 end = 0;
58 for(i = n-1 ; i >= 0 ; i --) {
59 end = end * len + strlen(str[i]);
60 }
61 printf("%d\n",bfs());
62 cas ++;
63 }
64 return 0;
65 }
HDU 1813 Escape from Tetris
IDA*的好题目，开始时没想到A*方法，就直接暴力的提交了一次，如愿超时，随便YY了一组case就跑不出结果，然后想到可以求出某个位置逃出的最少步数，然后在构造 h() 为所有点逃离迷宫的最少步数的最大值，然后很容易就能A掉了
View Code 1 #include 2 #include 3 using namespace std; 4 5 int n; 6 bool maze[10][10]; 7 int dir[4][2]={{0,1},{-1,0},{1,0},{0,-1}}; 8 9 int ans[100]; 10 int dis[10][10]; 11 int deep; 12 13 struct S{ 14 bool maze[10][10]; 15 S(){memset(maze,false,sizeof(maze));} 16 }s; 17 18 inline bool h(int d,S ts){ 19 for(int i=1;ideep){ 23 return false; 24 } 25 } 26 } 27 return true; 28 } 29 30 bool dfs(int d,S tu){ 31 if(!h(d,tu)) return false; 32 if(d==deep) return true; 33 for(int i=0;i<4;i++){ 34 S tv; 35 for(int ii=1;ii=n-1||ty>=n-1) continue; 67 if(!maze[tx][ty]) continue; 68 if(dis[tx][ty]<=dis[ux][uy]+1) continue; 69 dis[tx][ty]=dis[ux][uy]+1; 70 ee++; 71 que[ee][0]=tx; 72 que[ee][1]=ty; 73 } 74 } 75 } 76 77 inline void in(bool& val){ 78 char in=getchar(); 79 while(in<=32) in=getchar(); 80 val=(in=='0'); 81 } 82 83 int main(){ 84 bool flag=false; 85 while(~scanf("%d",&n)){ 86 for(int i=0;i
HDU 2918 Tobo or not Tobo
这题步数最多只有9步，果断IDA*，因为每步会改变四个数字的曼哈顿距离，所以h()构造为 (曼哈顿距离和+3)/4，提交竟然居首了
这题也可以用广搜预处理来写，广搜九层，然后询问时直接输出就好了，也可以0ms，但内存肯定要比IDA*大
View Code 1 #include 2 #include 3 using namespace std; 4 5 char maze[5][5]; 6 void cvrAc(){ 7 char tmp=maze[0][0]; 8 maze[0][0]=maze[1][0]; 9 maze[1][0]=maze[1][1]; 10 maze[1][1]=maze[0][1]; 11 maze[0][1]=tmp; 12 } 13 14 void cvrAr(){ 15 char tmp=maze[0][0]; 16 maze[0][0]=maze[0][1]; 17 maze[0][1]=maze[1][1]; 18 maze[1][1]=maze[1][0]; 19 maze[1][0]=tmp; 20 } 21 22 void cvrBc(){ 23 char tmp=maze[0][1]; 24 maze[0][1]=maze[1][1]; 25 maze[1][1]=maze[1][2]; 26 maze[1][2]=maze[0][2]; 27 maze[0][2]=tmp; 28 } 29 30 void cvrBr(){ 31 char tmp=maze[0][1]; 32 maze[0][1]=maze[0][2]; 33 maze[0][2]=maze[1][2]; 34 maze[1][2]=maze[1][1]; 35 maze[1][1]=tmp; 36 } 37 38 void cvrCc(){ 39 char tmp=maze[1][0]; 40 maze[1][0]=maze[2][0]; 41 maze[2][0]=maze[2][1]; 42 maze[2][1]=maze[1][1]; 43 maze[1][1]=tmp; 44 } 45 46 void cvrCr(){ 47 char tmp=maze[1][0]; 48 maze[1][0]=maze[1][1]; 49 maze[1][1]=maze[2][1]; 50 maze[2][1]=maze[2][0]; 51 maze[2][0]=tmp; 52 } 53 54 void cvrDc(){ 55 char tmp=maze[1][1]; 56 maze[1][1]=maze[2][1]; 57 maze[2][1]=maze[2][2]; 58 maze[2][2]=maze[1][2]; 59 maze[1][2]=tmp; 60 } 61 62 void cvrDr(){ 63 char tmp=maze[1][1]; 64 maze[1][1]=maze[1][2]; 65 maze[1][2]=maze[2][2]; 66 maze[2][2]=maze[2][1]; 67 maze[2][1]=tmp; 68 } 69 70 const int pos[][2]={{0,0},{0,1},{0,2},{1,0},{1,1},{1,2},{2,0},{2,1},{2,2}}; 71 inline int ABS(int x){ 72 if(x<0) return -x; 73 else return x; 74 } 75 int h(){ 76 int val=0; 77 for(int i=0;i<3;i++){ 78 for(int j=0;j<3;j++){ 79 int c=maze[i][j]-'1'; 80 val+=ABS(pos[c][0]-i)+ABS(pos[c][1]-j); 81 } 82 } 83 return val; 84 } 85 86 87 int deep; 88 bool dfs(int d){ 89 if(h()==0) return true; 90 if((h()+3)/4+d>deep) return false; 91 cvrAc(); 92 if(dfs(d+1)) return true; 93 cvrAr(); 94 cvrAr(); 95 if(dfs(d+1)) return true; 96 cvrAc(); 97 98 cvrBc(); 99 if(dfs(d+1)) return true;
100 cvrBr();
101 cvrBr();
102 if(dfs(d+1)) return true;
103 cvrBc();
104 105 cvrCc();
106 if(dfs(d+1)) return true;
107 cvrCr();
108 cvrCr();
109 if(dfs(d+1)) return true;
110 cvrCc();
111 112 cvrDc();
113 if(dfs(d+1)) return true;
114 cvrDr();
115 cvrDr();
116 if(dfs(d+1)) return true;
117 cvrDc();
118 119 return false;
120 }
121 122 char str[12];
123 int main(){
124 int cas=0;
125 while(~scanf("%s",str),strcmp(str,"0000000000")){
126 int mmax=str[0]-'0';
127 int p=1;
128 for(int i=0;i<3;i++){
129 for(int j=0;j<3;j++){
130 maze[i][j]=str[p++];
131 }
132 }
133 deep=0;
134 bool flag=false;
135 while(deep<=mmax){
136 if(dfs(0)){
137 flag=true;
138 break;
139 }
140 deep++;
141 }
142 printf("%d. ",++cas);
143 if(flag) printf("%d\n",deep);
144 else puts("-1");
145 }
146 }
HDU 3459 Rubik 2×2×2
这题是ReDow推荐的一道好玩的题目(ReDow大神无压力的占据着第一的位置)，用IDA*写，很容易想到一个很不给力的A*剪枝：因为有一块始终不会改变，可以确定3个面的颜色，根据这3个面的颜色又可以确定另外3个面的颜色，也就是说最终状态是确定的，这样可以在递归到最后3层时稍微起到点作用。跑sample都很吃力（这题都不要求是最优解，sample 20+步，而最优的16层就出结果了，还以为写错了，查代码查了半天- -），无意中提交了一下，sample都要卡一下下的代码竟然过了，200+ms。然后测了下不加A*的代码，跑了2s，看来这个A*还是很给力的
View Code 1 #include 2 #include 3 using namespace std; 4 5 char maze[10][10]; 6 void cvrX(){ 7 char tmp; 8 tmp=maze[0][3]; maze[0][3]=maze[3][6]; 9 maze[3][6]=maze[4][3]; maze[4][3]=maze[2][3]; maze[2][3]=tmp; 10 tmp=maze[1][3]; maze[1][3]=maze[2][6]; 11 maze[2][6]=maze[5][3]; maze[5][3]=maze[3][3]; maze[3][3]=tmp; 12 tmp=maze[2][4]; maze[2][4]=maze[2][5]; 13 maze[2][5]=maze[3][5]; maze[3][5]=maze[3][4]; maze[3][4]=tmp; 14 } 15 16 void cvrY(){ 17 char tmp; 18 tmp=maze[2][0]; maze[2][0]=maze[2][6]; 19 maze[2][6]=maze[2][4]; maze[2][4]=maze[2][2]; maze[2][2]=tmp; 20 tmp=maze[2][1]; maze[2][1]=maze[2][7]; 21 maze[2][7]=maze[2][5]; maze[2][5]=maze[2][3]; maze[2][3]=tmp; 22 tmp=maze[0][2]; maze[0][2]=maze[0][3]; 23 maze[0][3]=maze[1][3]; maze[1][3]=maze[1][2]; maze[1][2]=tmp; 24 } 25 26 void cvrZ(){ 27 char tmp; 28 tmp=maze[2][1]; maze[2][1]=maze[1][3]; 29 maze[1][3]=maze[3][4]; maze[3][4]=maze[4][2]; maze[4][2]=tmp; 30 tmp=maze[3][1]; maze[3][1]=maze[1][2]; 31 maze[1][2]=maze[2][4]; maze[2][4]=maze[4][3]; maze[4][3]=tmp; 32 tmp=maze[2][2]; maze[2][2]=maze[2][3]; 33 maze[2][3]=maze[3][3]; maze[3][3]=maze[3][2]; maze[3][2]=tmp; 34 } 35 36 bool check(){ 37 if(maze[0][3]!=maze[0][2]) return false; 38 if(maze[1][2]!=maze[0][2]) return false; 39 if(maze[1][3]!=maze[0][2]) return false; 40 41 if(maze[2][1]!=maze[2][0]) return false; 42 if(maze[3][0]!=maze[2][0]) return false; 43 if(maze[3][1]!=maze[2][0]) return false; 44 45 if(maze[2][3]!=maze[2][2]) return false; 46 if(maze[3][2]!=maze[2][2]) return false; 47 if(maze[3][3]!=maze[2][2]) return false; 48 49 if(maze[2][5]!=maze[2][4]) return false; 50 if(maze[3][4]!=maze[2][4]) return false; 51 if(maze[3][5]!=maze[2][4]) return false; 52 53 if(maze[2][7]!=maze[2][6]) return false; 54 if(maze[3][6]!=maze[2][6]) return false; 55 if(maze[3][7]!=maze[2][6]) return false; 56 57 if(maze[4][3]!=maze[4][2]) return false; 58 if(maze[5][2]!=maze[4][2]) return false; 59 if(maze[5][3]!=maze[4][2]) return false; 60 return true; 61 } 62 63 int h(){ 64 int cnt=0; 65 if(maze[5][3]!=maze[5][2]||maze[3][6]!=maze[3][7]) cnt++; 66 if(maze[2][7]!=maze[3][7]||maze[2][0]!=maze[3][0]) cnt++; 67 if(maze[3][0]!=maze[3][1]||maze[4][2]!=maze[5][2]) cnt++; 68 return cnt; 69 } 70 71 int deep; 72 char ans[100]; 73 bool dfs(int d){ 74 if(deep-d<=3&&d+h()>deep) return false; 75 if(d==deep) return check(); 76 77 cvrX(); 78 ans[d]='X'; 79 if(dfs(d+1)) return true; 80 cvrX(); cvrX(); cvrX(); 81 82 cvrY(); 83 ans[d]='Y'; 84 if(dfs(d+1)) return true; 85 cvrY(); cvrY(); cvrY(); 86 87 cvrZ(); 88 ans[d]='Z'; 89 if(dfs(d+1)) return true; 90 cvrZ(); cvrZ(); cvrZ(); 91 92 return false; 93 } 94 95 int main(){ 96 while(true){ 97 for(int i=0;i<6;i++){ 98 scanf("%s",maze[i]); 99 }
100 if(maze[0][2]=='.') break;
101 deep=0;
102 while(true){
103 if(dfs(0)) break;
104 deep++;
105 }
106 for(int i=0;i
A*、IDA*的也就这些了，别的一些搜索题目～
HDU 1401 Solitaire
一道经典的双广题目，去年暑假废了好大功夫写了一个很挫的200+ms的代码，今年再写就得心应手许多：
记录排序后的四个点的坐标作为当前状态，即8个小于8的数，用二进制(或者说是八进制)进行状态压缩，有近2kw种状态，用bitset进行hash，15ms过掉
View Code 1 #include 2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 8 bitset<20000010> vis[2]; 9 struct MAZE{ 10 int maze[4][2]; 11 12 MAZE(){} 13 MAZE(int m){ 14 for(int i=0;i<4;i++){ 15 for(int j=0;j<2;j++){ 16 maze[i][j]=m&7; 17 m>>=3; 18 } 19 } 20 } 21 22 unsigned zip(){ 23 unsigned ans=0,tmp[4]; 24 for(int i=0;i<4;i++) tmp[i]=(maze[i][1]<<3)+maze[i][0]; 25 sort(tmp,tmp+4); 26 for(int i=0;i<4;i++){ans<<=6;ans+=tmp[i];} 27 return ans; 28 } 29 }s,t; 30 31 queue qs,qt; 32 int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; 33 bool flag; 34 void bfs(queue& que,int d){ 35 int size=que.size(); 36 while(size--){ 37 int u=que.front(); que.pop(); 38 MAZE mu(u); 39 for(int i=0;i<4;i++){ 40 for(int j=0;j<4;j++){ 41 MAZE mv(mu); 42 mv.maze[i][0]+=dir[j][0]; 43 mv.maze[i][1]+=dir[j][1]; 44 if(mv.maze[i][0]<0||mv.maze[i][1]<0) continue; 45 if(mv.maze[i][0]>=8||mv.maze[i][1]>=8) continue; 46 bool can=true; 47 for(int ii=0;ii<4;ii++){ 48 if(ii==i) continue; 49 if(mv.maze[i][0]==mv.maze[ii][0]&&mv.maze[i][1]==mv.maze[ii][1]){ 50 mv.maze[i][0]+=dir[j][0]; 51 mv.maze[i][1]+=dir[j][1]; 52 if(mv.maze[i][0]<0||mv.maze[i][1]<0){can=false;break;} 53 if(mv.maze[i][0]>=8||mv.maze[i][1]>=8){can=true;break;} 54 for(int jj=0;jj<4;jj++){ 55 if(jj==i) continue; 56 if(mv.maze[i][0]==mv.maze[jj][0]&&mv.maze[i][1]==mv.maze[jj][1]){ 57 can=false; break; 58 } 59 } 60 } 61 } 62 if(can){ 63 int hv=mv.zip(); 64 if(vis[d][hv]) continue; 65 if(vis[d^1][hv]){flag=true;return;} 66 vis[d][hv]=true; 67 que.push(hv); 68 } 69 } 70 } 71 } 72 } 73 74 int main(){ 75 while(~scanf("%d%d",&s.maze[0][0],&s.maze[0][1])){ 76 s.maze[0][0]-=1; s.maze[0][1]-=1; 77 while(!qs.empty()) qs.pop(); 78 while(!qt.empty()) qt.pop(); 79 for(int i=1;i<4;i++){ 80 scanf("%d%d",&s.maze[i][0],&s.maze[i][1]); 81 s.maze[i][0]-=1; s.maze[i][1]-=1; 82 } 83 for(int i=0;i<4;i++){ 84 scanf("%d%d",&t.maze[i][0],&t.maze[i][1]); 85 t.maze[i][0]-=1; t.maze[i][1]-=1; 86 } 87 88 int szip=s.zip(); 89 int tzip=t.zip(); 90 qs.push(szip); 91 qt.push(tzip); 92 if(szip==tzip){ 93 puts("YES"); 94 continue; 95 } 96 vis[0].reset(); 97 vis[1].reset(); 98 vis[0][szip]=1; 99 vis[1][tzip]=1;
100 flag=false;
101 int cnt=8;
102 while(cnt--){
103 if(qs.size()<=qt.size()) bfs(qs,0);
104 else bfs(qt,1);
105 if(flag) break;
106 }
107 puts(flag?"YES":"NO");
108 }
109 }
HDU 1430 魔板
数据量很大的一道题，双广要跑2s+而且还要记录路径，代码过烦了，参考hh博客知道预处理的方法：
由于只是8种颜色，所以标号就无所谓了，对起始状态重新修改标号为 12345678(别的也行)，对目标状态标号做相应的修改，先预处理出12345678到所有状态的路径，记录所有状态的pre值，直接输出即可；其实以目标状态为标准去修改起始状态标号可以省去逆序输出路径的麻烦
View Code 1 #include 2 #include 3 #include 4 #include 5 using namespace std; 6 7 char smaze[10],tmaze[10]; 8 bool vis[50000]; 9 const int fac[]={1,1,2,6,24,120,720,5040,40320}; 10 int inv_hash(char str[]){ 11 int ans=0; 12 for(int i=0;i<8;i++){ 13 int cnt=0; 14 for(int k=i-1;k>=0;k--){ 15 if(str[k]>str[i]) cnt++; 16 } 17 ans+=fac[i]*cnt; 18 } 19 return ans; 20 } 21 22 struct Node{ 23 char str[10]; 24 Node(){} 25 Node(char _s[]){ 26 for(int i=0;i<8;i++){ 27 str[i]=_s[i]; 28 } 29 } 30 }; 31 32 void cvrA(Node& n){ 33 reverse(n.str,n.str+8); 34 } 35 36 void cvrB(Node& n){ 37 char tmp; 38 tmp=n.str[0]; n.str[0]=n.str[3]; n.str[3]=n.str[2]; 39 n.str[2]=n.str[1]; n.str[1]=tmp; 40 tmp=n.str[4]; n.str[4]=n.str[5]; n.str[5]=n.str[6]; 41 n.str[6]=n.str[7]; n.str[7]=tmp; 42 } 43 44 void cvrC(Node& n){ 45 char tmp=n.str[1]; n.str[1]=n.str[6]; n.str[6]=n.str[5]; 46 n.str[5]=n.str[2]; n.str[2]=tmp; 47 } 48 49 int pre[50000]; 50 char ctrl[50000]; 51 void bfs(){ 52 memset(vis,false,sizeof(vis)); 53 queue que; 54 que.push(Node("12345678")); 55 vis[0]=true; 56 while(!que.empty()){ 57 Node u=que.front(); que.pop(); 58 int uh=inv_hash(u.str); 59 Node v(u); 60 cvrA(v); 61 int vh=inv_hash(v.str); 62 if(!vis[vh]){ 63 vis[vh]=true; 64 pre[vh]=uh; 65 ctrl[vh]='A'; 66 que.push(v); 67 } 68 69 v=u; 70 cvrB(v); 71 vh=inv_hash(v.str); 72 if(!vis[vh]){ 73 vis[vh]=true; 74 pre[vh]=uh; 75 ctrl[vh]='B'; 76 que.push(v); 77 } 78 79 v=u; 80 cvrC(v); 81 vh=inv_hash(v.str); 82 if(!vis[vh]){ 83 vis[vh]=true; 84 pre[vh]=uh; 85 ctrl[vh]='C'; 86 que.push(v); 87 } 88 } 89 } 90 91 char stk[1000]; 92 int pmaze[10]; 93 int main(){ 94 bfs(); 95 while(~scanf("%s %s",smaze,tmaze)){ 96 for(int i=0;i<8;i++) pmaze[smaze[i]-'1']=i; 97 for(int i=0;i<8;i++) tmaze[i]=pmaze[tmaze[i]-'1']+'1'; 98 Node tN=Node(tmaze); 99 int tmp=inv_hash(tN.str);
100 int t=0;
101 while(tmp){
102 stk[t++]=ctrl[tmp];
103 tmp=pre[tmp];
104 }
105 while(t--) putchar(stk[t]);
106 puts("");
107 }
108 }
HDU 3567 Eight II
Eight 的加强版
做过魔板这题再做这题，脑子里就只有预处理的方法了，因为这题有一个特殊的点X，所以枚举X的位置，打出9张前驱表，用魔板题一样的方法将两个状态的对应标号转化，输出就好了，800ms
View Code 1 #include 2 #include 3 #include 4 using namespace std; 5 6 struct S{ 7 char maze[3][3]; 8 int x,y; 9 10 S(){} 11 S(const char *str){ 12 for(int i=0,tx=0,ty=0;str[i];i++){ 13 maze[tx][ty]=str[i]; 14 if(str[i]=='X'){x=tx;y=ty;} 15 ty++;if(ty==3){ty=0;tx++;} 16 } 17 } 18 }; 19 int pre[10][363000]; 20 char op[10][363000]; 21 22 const int fac[]={1,1,2,6,24,120,720,5040,40320}; 23 bool vis[363000]; 24 inline int inv_hash(S ts){ 25 char str[10]; int ans=0; 26 for(int i=0;i<3;i++){ 27 for(int j=0;j<3;j++){ 28 str[i*3+j]=ts.maze[i][j]; 29 int cnt=0; 30 for(int k=i*3+j-1;k>=0;k--){ 31 if(str[k]>str[i*3+j]) cnt++; 32 } 33 ans+=fac[i*3+j]*cnt; 34 } 35 } 36 return ans; 37 } 38 39 S s; 40 const int dir[4][2]={{1,0},{0,-1},{0,1},{-1,0}}; 41 const char cdir[]="dlru"; 42 void bfs(int x){ 43 memset(pre[x],-1,sizeof(pre[x])); 44 memset(vis,false,sizeof(vis)); 45 46 queue que; 47 que.push(s); 48 vis[inv_hash(s)]=true; 49 while(!que.empty()){ 50 S u=que.front(); que.pop(); 51 int ihu=inv_hash(u); 52 for(int i=0;i<4;i++){ 53 S v=u; 54 v.x+=dir[i][0]; 55 v.y+=dir[i][1]; 56 if(v.x<0||v.y<0||v.x>=3||v.y>=3) continue; 57 v.maze[u.x][u.y]=v.maze[v.x][v.y]; 58 v.maze[v.x][v.y]='X'; 59 int ihv=inv_hash(v); 60 if(vis[ihv]) continue; 61 vis[ihv]=true; 62 pre[x][ihv]=ihu; 63 op[x][ihv]=cdir[i]; 64 que.push(v); 65 } 66 } 67 } 68 69 char in[100]; 70 char stk[100]; 71 int cvr[10]; 72 int main(){ 73 s=S("X12345678"); bfs(0); 74 s=S("1X2345678"); bfs(1); 75 s=S("12X345678"); bfs(2); 76 s=S("123X45678"); bfs(3); 77 s=S("1234X5678"); bfs(4); 78 s=S("12345X678"); bfs(5); 79 s=S("123456X78"); bfs(6); 80 s=S("1234567X8"); bfs(7); 81 s=S("12345678X"); bfs(8); 82 83 int t,cas=0; 84 scanf("%d",&t); 85 while(t--){ 86 int p; 87 scanf("%s",in); 88 for(int i=0,j=0;in[i];i++){ 89 if(in[i]!='X') cvr[in[i]-'0']=j++; 90 else p=i; 91 } 92 scanf("%s",in); 93 for(int i=0;in[i];i++){ 94 if(in[i]=='X') continue; 95 in[i]=cvr[in[i]-'0']+'1'; 96 } 97 s=S(in); 98 int ihs=inv_hash(s); 99 int top=-1,tmp=ihs;
100 while(tmp!=-1){
101 stk[++top]=op[p][tmp];
102 tmp=pre[p][tmp];
103 }
104 printf("Case %d: %d\n",++cas,top);
105 while((--top)!=-1){
106 putchar(stk[top]);
107 }
108 puts("");
109 }
110 }
HDU 2691 2-Dimensional Rubik's Cube
这题是3459的加强版，双广，状态太多了，试了几种字符串hash都有冲突，sample都出不来，只好改用map，跑了3s+，后来问了hh，因为只有六种颜色，可以将每种状态转换成一个long long型，6^24，可以用散列表hash。我的代码～
View Code 1 #include 2 #include 3 #include 4 #include
最新评论