突然发现八数码难题挺有意思的
貌似关于这一个问题就能延伸出好多种算法
挖个坑,慢慢填2333
第一发
裸的BFS
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<queue>
5 #include<map>
6 #include<cstdlib>
7 using namespace std;
8 const int n=3;
9 inline void read(int &n)
10 {
11 char c=getchar();bool flag=0;n=0;
12 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
13 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
14 }
15 map<string,bool>vis;
16 struct node
17 {
18 int a[4][4];
19 int step;
20 }cur,nxt,ed;
21 inline void debug(node p)
22 {
23 printf("***********\n");
24 for(int i=1;i<=n;i++)
25 {
26 for(int j=1;j<=n;j++)
27 printf("%d ",p.a[i][j]);
28 putchar('\n');
29 }
30 printf("***********\n");
31 }
32 int xx[5]={-1,+1,0,0};
33 int yy[5]={0,0,-1,+1};
34 bool pd(node p)
35 {
36 string s;
37 for(int i=1;i<=n;i++)
38 for(int j=1;j<=n;j++)
39 s=s+(char)(p.a[i][j]-48);
40 if(vis[s]==0){ vis[s]=1;return 0; }
41 else return 1;
42 }
43 bool findans(node p)
44 {
45 for(int i=1;i<=n;i++)
46 for(int j=1;j<=n;j++)
47 if(p.a[i][j]!=ed.a[i][j]) return 0;
48 return 1;
49 }
50 inline void BFS()
51 {
52 queue<node>q;
53 q.push(cur);
54 while(q.size()!=0)
55 {
56 node p=q.front();
57 //debug(p);
58 if(findans(p)==1)
59 {
60 printf("%d",p.step);
61 exit(0);
62 }
63 q.pop();
64 bool flag=0;
65 for(int i=1;i<=n;i++)
66 {
67 for(int j=1;j<=n;j++)
68 {
69 if(p.a[i][j]==0)
70 {
71 for(int k=0;k<4;k++)
72 {
73 int wx=i+xx[k];
74 int wy=j+yy[k];
75 if(wx>=1&&wx<=n&&wy>=1&&wy<=n)
76 {
77 node nxt=p;
78 swap(nxt.a[i][j],nxt.a[wx][wy]);
79 nxt.step=p.step+1;
80 if( pd(nxt) == 0 )
81 q.push(nxt);
82 }
83 }
84 flag=1;break;
85 }
86 }
87 if(flag==1) break;
88 }
89
90 }
91 }
92 int main()
93 {
94 ed.a[1][1]=1;ed.a[1][2]=2;ed.a[1][3]=3;ed.a[2][1]=8;ed.a[2][2]=0;ed.a[2][3]=4;ed.a[3][1]=7;ed.a[3][2]=6;ed.a[3][3]=5;
95 for(int i=1;i<=n;i++)
96 for(int j=1;j<=n;j++)
97 { char c=getchar();cur.a[i][j]=c-48; }
98 cur.step=0;
99 BFS();
100 return 0;
101 }
第一次
第二次
第三次
慢的一逼。。
第二次TLE了5个点,,
表示实在无力吐槽啊。。。
我的代码有这么丑么???
不行!我要优化!!
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<queue>
5 #include<map>
6 #include<cstdlib>
7 using namespace std;
8 const int n=3;
9 inline void read(int &n)
10 {
11 char c=getchar();bool flag=0;n=0;
12 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
13 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
14 }
15 map<string,bool>vis;
16 struct node
17 {
18 int a[4][4];
19 int step;
20 int zerox,zeroy;
21 }cur,nxt,ed;
22 inline void debug(node p)
23 {
24 printf("***********\n");
25 for(int i=1;i<=n;i++)
26 {
27 for(int j=1;j<=n;j++)
28 printf("%d ",p.a[i][j]);
29 putchar('\n');
30 }
31 printf("***********\n");
32 }
33 int xx[5]={-1,+1,0,0};
34 int yy[5]={0,0,-1,+1};
35 bool pd(node p)
36 {
37 string s;
38 for(int i=1;i<=n;i++)
39 for(int j=1;j<=n;j++)
40 s=s+(char)(p.a[i][j]-48);
41 if(vis[s]==0){ vis[s]=1;return 0; }
42 else return 1;
43 }
44 bool findans(node p)
45 {
46 for(int i=1;i<=n;i++)
47 for(int j=1;j<=n;j++)
48 if(p.a[i][j]!=ed.a[i][j]) return 0;
49 return 1;
50 }
51 inline void BFS()
52 {
53 queue<node>q;
54 q.push(cur);
55 while(q.size()!=0)
56 {
57 node p=q.front();
58 //debug(p);
59 if(findans(p)==1)
60 {
61 printf("%d",p.step);
62 exit(0);
63 }
64 q.pop();
65 bool flag=0;
66 for(int k=0;k<4;k++)
67 {
68 int wx=p.zerox+xx[k];
69 int wy=p.zeroy+yy[k];
70 if(wx>=1&&wx<=n&&wy>=1&&wy<=n)
71 {
72 node nxt=p;
73 swap(nxt.a[p.zerox][p.zeroy],nxt.a[wx][wy]);
74 nxt.step=p.step+1;
75 nxt.zerox=wx;nxt.zeroy=wy;
76 if( pd(nxt) == 0 )
77 q.push(nxt);
78 }
79 }
80 }
81 }
82 int main()
83 {
84 ed.a[1][1]=1;ed.a[1][2]=2;ed.a[1][3]=3;ed.a[2][1]=8;ed.a[2][2]=0;ed.a[2][3]=4;ed.a[3][1]=7;ed.a[3][2]=6;ed.a[3][3]=5;
85 for(int i=1;i<=n;i++)
86 for(int j=1;j<=n;j++)
87 { char c=getchar();cur.a[i][j]=c-48;
88 if(c=='0') cur.zerox=i,cur.zeroy=j;
89 }
90 cur.step=0;
91 BFS();
92 return 0;
93 }
这次我把寻找0的位置的循环给去掉了,
用两个变量来记录0的位置,用空间换时间
第一次
第二次
第三次
WTF?????
卵用没有????
=.=。。。。。
=.=。。。。。,,,,
看来常数优化是没怎么有用了
尝试优化一下STL吧
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<queue>
5 #include<map>
6 #include<cstdlib>
7 using namespace std;
8 const int n=3;
9 inline void read(int &n)
10 {
11 char c=getchar();bool flag=0;n=0;
12 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
13 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
14 }
15 struct node
16 {
17 int a[4][4];
18 int step;
19 int zerox,zeroy;
20 }cur,nxt,ed;
21 inline void debug(node p)
22 {
23 printf("***********\n");
24 for(int i=1;i<=n;i++)
25 {
26 for(int j=1;j<=n;j++)
27 printf("%d ",p.a[i][j]);
28 putchar('\n');
29 }
30 printf("***********\n");
31 }
32 int xx[5]={-1,+1,0,0};
33 int yy[5]={0,0,-1,+1};
34 int vis[37338030];
35 bool pd(node p)
36 {
37 unsigned int seed=0;
38 unsigned long long k=1;
39 for(int i=1;i<=n;i++)
40 for(int j=1;j<=n;j++)
41 seed=seed+p.a[i][j]*k,k=k*9;
42 seed=(seed%3733801);
43 if(vis[seed]==0){ vis[seed]=1;return 0; }
44 else return 1;
45 }
46 bool findans(node p)
47 {
48 for(int i=1;i<=n;i++)
49 for(int j=1;j<=n;j++)
50 if(p.a[i][j]!=ed.a[i][j]) return 0;
51 return 1;
52 }
53 inline void BFS()
54 {
55 queue<node>q;
56 q.push(cur);
57 while(q.size()!=0)
58 {
59 node p=q.front();
60 //debug(p);
61 if(findans(p)==1)
62 {
63 printf("%d",p.
64 step);
65 exit(0);
66 }
67 q.pop();
68 bool flag=0;
69 for(int k=0;k<4;k++)
70 {
71 int wx=p.zerox+xx[k];
72 int wy=p.zeroy+yy[k];
73 if(wx>=1&&wx<=n&&wy>=1&&wy<=n)
74 {
75 node nxt=p;
76 swap(nxt.a[p.zerox][p.zeroy],nxt.a[wx][wy]);
77 nxt.step=p.step+1;
78 nxt.zerox=wx;nxt.zeroy=wy;
79 if( pd(nxt) == 0 )
80 q.push(nxt);
81 }
82 }
83 }
84 }
85 int main()
86 {
87 ed.a[1][1]=1;ed.a[1][2]=2;ed.a[1][3]=3;ed.a[2][1]=8;ed.a[2][2]=0;ed.a[2][3]=4;ed.a[3][1]=7;ed.a[3][2]=6;ed.a[3][3]=5;
88 for(int i=1;i<=n;i++)
89 for(int j=1;j<=n;j++)
90 { char c=getchar();cur.a[i][j]=c-48;
91 if(c=='0') cur.zerox=i,cur.zeroy=j;
92 }
93 cur.step=0;
94 BFS();
95 return 0;
96 }
果断把map改成hash
老师说过map慢的一逼
第一次
第二次
第三次
O__O" O__O" O__O" O__O"
O__O" O__O" O__O" O__O"
O__O" O__O" O__O" O__O"
O__O" O__O" O__O" O__O"
O__O" O__O" O__O" O__O"
=.=...
发生了什么,,,我只不过是优化了一个理论上的log而已=.=。。
不会吧,,,,,
我以前可都是用map+string判重的。。。
我感觉我需要重新认识一下这个世界了。。。。
zhx老师说过倒着搜会有神奇的效果。
不如试一试?
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<queue>
5 #include<map>
6 #include<cstdlib>
7 using namespace std;
8 const int n=3;
9 inline void read(int &n)
10 {
11 char c=getchar();bool flag=0;n=0;
12 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
13 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
14 }
15 struct node
16 {
17 int a[4][4];
18 int step;
19 int zerox,zeroy;
20 }cur,nxt,ed;
21 inline void debug(node p)
22 {
23 printf("***********\n");
24 for(int i=1;i<=n;i++)
25 {
26 for(int j=1;j<=n;j++)
27 printf("%d ",p.a[i][j]);
28 putchar('\n');
29 }
30 printf("***********\n");
31 }
32 int xx[5]={-1,+1,0,0};
33 int yy[5]={0,0,-1,+1};
34 int vis[5733801];
35 bool pd(node p)
36 {
37 unsigned int seed=0;
38 unsigned long long k=1;
39 for(int i=1;i<=n;i++)
40 for(int j=1;j<=n;j++)
41 seed=seed+p.a[i][j]*k,k=k*71;
42 seed=(seed%5733801);
43 if(vis[seed]==0){ vis[seed]=1;return 0; }
44 else return 1;
45 }
46 bool findans(node p)
47 {
48 for(int i=1;i<=n;i++)
49 for(int j=1;j<=n;j++)
50 if(p.a[i][j]!=ed.a[i][j]) return 0;
51 return 1;
52 }
53 inline void BFS()
54 {
55 queue<node>q;
56 q.push(cur);
57 while(q.size()!=0)
58 {
59 node p=q.front();
60 //debug(p);
61 if(findans(p)==1)
62 {
63 printf("%d",p.
64 step);
65 exit(0);
66 }
67 q.pop();
68 bool flag=0;
69 for(int k=0;k<4;k++)
70 {
71 int wx=p.zerox+xx[k];
72 int wy=p.zeroy+yy[k];
73 if(wx>=1&&wx<=n&&wy>=1&&wy<=n)
74 {
75 node nxt=p;
76 swap(nxt.a[p.zerox][p.zeroy],nxt.a[wx][wy]);
77 nxt.step=p.step+1;
78 nxt.zerox=wx;nxt.zeroy=wy;
79 if( pd(nxt) == 0 )
80 q.push(nxt);
81 }
82 }
83 }
84 }
85 int main()
86 {
87 ed.a[1][1]=1;ed.a[1][2]=2;ed.a[1][3]=3;ed.a[2][1]=8;ed.a[2][2]=0;ed.a[2][3]=4;ed.a[3][1]=7;ed.a[3][2]=6;ed.a[3][3]=5;
88 ed.zerox=2;ed.zeroy=2;
89 for(int i=1;i<=n;i++)
90 for(int j=1;j<=n;j++)
91 { char c=getchar();cur.a[i][j]=c-48;
92 if(c=='0') cur.zerox=i,cur.zeroy=j;
93 }
94 swap(ed,cur);
95 cur.step=0;
96 BFS();
97 return 0;
98 }
时间复杂度应该是差不多的
看来需要从算法上进行优化了
一种比较神奇的算法,关于他的介绍可以看http://blog.csdn.net/zgwangbo/article/details/52078338
对于这道题来说,我们可以枚举一个希望的值,再进行枚举
注意枚举的时候要用DFS,因为BFS不好记录状态
(无视ID)
雾。。。
和爆搜差不多,,,
我的代码有这么丑么。。。。
貌似快了一些
好像又快了一些。。。
但还是比估计的慢很多
我去!!
我终于知道为什么慢了
我在取绝对值的时候是用的自己手写的fabs
用了algorithm库里面的之后快了接近300ms!
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<cmath>
6 using namespace std;
7 const int n=3;
8 inline void read(int &n)
9 {
10 char c=getchar();bool flag=0;n=0;
11 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
12 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
13 }
14 int xx[4]={0,1,-1,0};
15 int yy[4]={1,0,0,-1};
16 int fx[11]={0,1,1,1,2,3,3,3,2};
17 int fy[11]={0,1,2,3,3,3,2,1,1};// fx[i] fy[j]表示的是目标状态下i数码的位置
18 int a[4][4];
19 int check()
20 {
21 int now=0;
22 for(int i=1;i<=3;i++)
23 for(int j=1;j<=3;j++)
24 if(a[i][j])
25 now+=abs(i-fx[a[i][j]])+abs(j-fy[a[i][j]]);
26 return now;
27 }
28 int ans=0;
29 void dfs(int k,int zerox,int zeroy,int step)
30 {
31 int h=check();
32 if(h==0)
33 {
34 ans=step;return ;
35 }
36 if(h+step>k||ans||step==k) return ;
37 for(int i=0;i<4;i++)
38 {
39 int wx=zerox+xx[i];
40 int wy=zeroy+yy[i];
41 if(wx>=1&&wx<=n&&wy>=1&&wy<=n)
42 {
43 swap(a[zerox][zeroy],a[wx][wy]);
44 dfs(k,wx,wy,step+1);
45 swap(a[zerox][zeroy],a[wx][wy]);
46 }
47 }
48 }
49 int main()
50 {
51 int zerox,zeroy,k=0;
52 char c;
53 for(int i=1;i<=n;i++)
54 for(int j=1;j<=n;j++)
55 { scanf("%c",&c);a[i][j]=c-48;
56 if(c=='0') zerox=i,zeroy=j;}
57 while(++k&&ans==0)
58 dfs(k,zerox,zeroy,0);
59 printf("%d",ans);
60 return 0;
61 }