首页 > > 程序设计 > C/C++ >

八数码难题解法大全

2018-06-17 21:44:10来源：未知 阅读 ()

新老客户大回馈,云服务器低至5折

暂时弃坑，双向广搜太**难写了。。。。

https://www.luogu.org/problem/show?pid=1379

突然发现八数码难题挺有意思的

貌似关于这一个问题就能延伸出好多种算法

挖个坑，慢慢填2333

BFS+map

第一发

裸的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 }
BFS+map

第一次

第二次

第三次

 慢的一逼。。

第二次TLE了5个点，，

表示实在无力吐槽啊。。。

我的代码有这么丑么？？？

不行！我要优化！！

BFS+map+常数优化

 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 }
BFS+map+常数优化

这次我把寻找0的位置的循环给去掉了，

用两个变量来记录0的位置，用空间换时间

第一次

第二次

 

第三次

 

 

 WTF？？？？？

卵用没有？？？？

=.=。。。。。

=.=。。。。。，，，，

看来常数优化是没怎么有用了

尝试优化一下STL吧

BFS+hash

 

 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改成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老师说过倒着搜会有神奇的效果。
不如试一试？

BFS+hash+逆向搜索

 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 }
BFS+hash+逆向搜索

 

 时间复杂度应该是差不多的

看来需要从算法上进行优化了

 

 

 A*

一种比较神奇的算法，关于他的介绍可以看http://blog.csdn.net/zgwangbo/article/details/52078338

对于这道题来说，我们可以枚举一个希望的值，再进行枚举

注意枚举的时候要用DFS，因为BFS不好记录状态

 

裸的A*

(无视ID)

雾。。。

和爆搜差不多，，，

我的代码有这么丑么。。。。

 

拆开结构体

貌似快了一些

把变量加到dfs的参数中

 

好像又快了一些。。。

但还是比估计的慢很多

 

 

真相大白

我去！！

我终于知道为什么慢了

我在取绝对值的时候是用的自己手写的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 }
最终版本

 

 

 

 

 

 

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有

上一篇：cin、cin.get()、cin.getline()的区分

下一篇：洛谷P1311 选择客栈

相关文章

IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设

网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源

网站联盟： 联盟新闻 联盟介绍 联盟点评 网赚技巧

行业资讯： 搜索引擎 网络游戏 电子商务 广告传媒

网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它

服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护

软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷

网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash

程序设计： Java技术 C/C++ VB delphi

网络知识： 网络协议 网络安全 网络管理 组网方案 Cisco技术

操作系统： Win2000 WinXP Win2003 Mac OS Linux FreeBSD

热门词条
最新资讯
热门关注
热门标签