P1379 八数码难题

admin

https://www.luogu.org/problemnew/show/P1379
题目描述
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入输出格式
输入格式：
输入初始状态，一行九个数字，空格用0表示

输出格式：
只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)

输入输出样例
输入样例#1：
283104765
输出样例#1：
4

我写的标准的单向广搜，效率不高，正确性是显然的。大家可以学学

1. #include <iostream>
   
2. using namespace std;
   
3. const int mm=10100;
   
4. string d[mm];  ///表示状态
   
5. int f[mm];///表示他的爸爸
   
6. int head,tail;
   
7. bool b;
   
8. string s,t; ///源和目标
   
9. string ts,tt;
   
10. string change(string s,int i)
    
11. {
    
12.     ///1,2,3,4 分别表示空格向上右下左运动
    
13.     int x=s.find('0');
    
14.     string tt=s;
    
15.     if (i==1) ///向上
    
16.     {
    
17.         if (x>2)  ///要求不在第一行
    
18.             swap(tt[x],tt[x-3]);
    
19.     }
    
20.     if (i==2)
    
21.     {
    
22.         if (x%3<2) ///要求不在最后一列
    
23.             swap(tt[x],tt[x+1]);
    
24.     }
    
25.     if (i==3)
    
26.     {
    
27.         if (x/3<2) ///要求不在最后一行
    
28.             swap(tt[x],tt[x+3]);
    
29.     }
    
30.     if (i==4)
    
31.     {
    
32.         if (x%3>0) ///要求不在第一列
    
33.             swap(tt[x],tt[x-1]);
    
34.     }
    
35.     return tt;
    
36. }
    
37. bool isdup(string s)
    
38. {
    
39.     bool b=0;
    
40.     for (int i=1; i<=tail; i++)
    
41.         if (d[i]==s)
    
42.         {
    
43.             b=1;
    
44.             break;
    
45.         }
    
46.     return b;
    
47. }
    
48. void pp()
    
49. {
    
50.     int i=1,j;
    
51.     int p[50];///最多50步，表示路径
    
52.     p[1]=j=head;
    
53.     while (f[j]!=0)
    
54.         p[++i]=j=f[j];
    
55.     cout<<i;
    
56. }
    
57. int main()
    
58. {
    
59.     s="123804765";
    
60.     cin>>t; ///读入状态
    
61.     head=tail=1;
    
62.     d[head]=s; ///初始状态入队
    
63.     f[head]=0;
    
64.     b=1;///未找到标记
    
65.     if (s==t) cout<<0;
    
66.     else
    
67.     {
    
68.         while (tail<=mm-1000  && tail>=head  && b)
    
69.         {
    
70.             ts=d[head]; ///取队首元素
    
71.             ///cout<<ts<<endl;  输出检查
    
72.             for (int i=1; i<=4; i++)  ///按规则扩展
    
73.             {
    
74.                 tt=change(ts,i);
    
75.                 if (tt==t)
    
76.                 {
    
77.                     b=0;    ///达到终点，跳出
    
78.                     break;
    
79.                 }
    
80.                 if (!isdup(tt)) ///判重入队
    
81.                 {
    
82.                     tail++;
    
83.                     d[tail]=tt;
    
84.                     f[tail]=head;
    
85.                 }
    
86.             }
    
87.             head++;
    
88.         }
    
89.         if (!b) pp();
    
90.     }
    
91.     return 0;
    
92. 
    
93. }
    

复制代码

加上map优化的话，可以得90分。

1. #include <iostream>
   
2. #include<map>
   
3. using namespace std;
   
4. const int mm=10100;
   
5. string d[mm];  ///表示状态
   
6. int f[mm];///表示他的爸爸
   
7. int head,tail;
   
8. bool b;
   
9. string s,t; ///源和目标
   
10. string ts,tt;///临时
    
11. map<string,int> m;  ///判重！！！
    
12. string change(string s,int i)
    
13. {
    
14.     ///1,2,3,4 分别表示空格向上右下左运动
    
15.     int x=s.find('0');
    
16.     string tt=s;
    
17.     if (i==1) ///向上
    
18.     {
    
19.         if (x>2)  ///要求不在第一行
    
20.             swap(tt[x],tt[x-3]);
    
21.     }
    
22.     if (i==2)
    
23.     {
    
24.         if (x%3<2) ///要求不在最后一列
    
25.             swap(tt[x],tt[x+1]);
    
26.     }
    
27.     if (i==3)
    
28.     {
    
29.         if (x/3<2) ///要求不在最后一行
    
30.             swap(tt[x],tt[x+3]);
    
31.     }
    
32.     if (i==4)
    
33.     {
    
34.         if (x%3>0) ///要求不在第一列
    
35.             swap(tt[x],tt[x-1]);
    
36.     }
    
37.     return tt;
    
38. }
    
39. void pp()
    
40. {
    
41.     int i=1,j;
    
42.     int p[50];///最多50步，表示路径
    
43.     p[1]=j=head;
    
44.     while (f[j]!=0)
    
45.         p[++i]=j=f[j];
    
46.     cout<<i;
    
47. }
    
48. int main()
    
49. {
    
50.     s="123804765";
    
51.     cin>>t; ///读入状态
    
52.     head=tail=1;
    
53.     d[head]=s; ///初始状态入队
    
54.     f[head]=0;
    
55.     b=1;///未找到标记
    
56.     if (s==t) cout<<0;
    
57.     else
    
58.     {
    
59.         while (tail<=mm-1000  && tail>=head  && b)
    
60.         {
    
61.             ts=d[head]; ///取队首元素
    
62.             ///cout<<ts<<endl;  输出检查
    
63.             for (int i=1; i<=4; i++)  ///按规则扩展
    
64.             {
    
65.                 tt=change(ts,i);
    
66.                 if (tt==t)
    
67.                 {
    
68.                     b=0;    ///达到终点，跳出
    
69.                     break;
    
70.                 }
    
71.                 if (m.find(tt)==m.end()) ///判重入队
    
72.                 {
    
73.                     m.insert(pair<string,int> (tt,head));
    
74.                     tail++;
    
75.                     d[tail]=tt;
    
76.                     f[tail]=head;
    
77.                 }
    
78.             }
    
79.             head++;
    
80.         }
    
81.         if (!b) pp();
    
82.     }
    
83.     return 0;
    
84. 
    
85. }
    

复制代码

张乐天

1. #include<iostream>
   
2. #include<cstdio>
   
3. #include<map>
   
4. using namespace std;
   
5. string r="123804765";
   
6. map<string,int>m;
   
7. string a[1000000];///状态
   
8. int b[1000000];///次数
   
9. int h=1,t=2;
   
10. bool bb=1;
    
11. string change(int i,string k)///移动
    
12. {
    
13.     string tt=k;
    
14.     int x=tt.find('0');
    
15.     if(i==1&&x<=5)swap(tt[x],tt[x+3]);
    
16.     if(i==2&&x>=3)swap(tt[x],tt[x-3]);
    
17.     if(i==3&&x%3>=1)swap(tt[x],tt[x-1]);
    
18.     if(i==4&&x%3<=1)swap(tt[x],tt[x+1]);
    
19.     return tt;
    
20. }
    
21. int main()
    
22. {
    
23.     cin>>a[1];
    
24.     b[1]=0;
    
25.     if(a[1]==r)
    
26.     {
    
27.         cout<<0<<endl;
    
28.         return 0;
    
29.     }
    
30.     while(h<=t&&t<=900000&&bb)
    
31.     {
    
32.         string xs=a[h];
    
33.         int xa=b[h];
    
34.         for(int i=1;i<=4;++i)
    
35.         {
    
36.             string tt=change(i,xs);
    
37.             int tc=xa+1;
    
38.             if(m.count(tt))continue;
    
39.             else
    
40.             {
    
41.                 m.insert(pair<string,int>(tt,tc));
    
42.                 a[t]=tt;
    
43.                 b[t]=tc;
    
44.                 if(a[t]==r)
    
45.                 {
    
46.                     cout<<b[t]<<endl;
    
47.                     bb=false;
    
48.                     return 0;       
    
49.                 }
    
50.                 t++;
    
51.             }
    
52.         }
    
53.         h++;
    
54.     }
    
55.     return 0;
    
56. }

复制代码

张溯源

老师，这个后面一个程序（map），我试了一下，只能有19分

张溯源

老师，这个程序看是看得懂，问题是全部超时了，开了优化之后，全不错了，满分程序怎么写

黄煦喆

1. #include<iostream>//123804765
   
2. #include<queue>
   
3. #include<map>
   
4. using namespace std;
   
5. string s,ss,ts,goal="123804765",tt;
   
6. queue<string>q;
   
7. map<string,int>m;
   
8. bool b;
   
9. string change(string x,int i)
   
10. {
    
11.     int num=x.find('0');
    
12.     ts=x;
    
13.     if(i==1&&num>2)swap(ts[num],ts[num-3]);
    
14.     else if(i==2&&num%3!=2)swap(ts[num],ts[num+1]);
    
15.     else if(i==3&&num<6)swap(ts[num],ts[num+3]);
    
16.     else if(i==4&&num%3!=0)swap(ts[num],ts[num-1]);
    
17.     return ts;
    
18. }
    
19. int main()
    
20. {
    
21.     cin>>s;
    
22.     q.push(s);
    
23.     m[s]=1;
    
24.     while(!q.empty()&&!b)
    
25.     {
    
26.         tt=q.front();
    
27.         q.pop();
    
28.         if(tt==goal)b=1;
    
29.         else for(int i=1; i<=4; i++)
    
30.             {
    
31.                 ss=change(tt,i);
    
32.                 if(m[ss]==0)q.push(ss),m[ss]=m[tt]+1;
    
33.             }
    
34.     }
    
35.     cout<<m[goal]-1;
    
36.     return 0;
    
37. }
    

复制代码

YTC

单广搜居然能卡过

1. #include<iostream>
   
2. #include<queue>
   
3. #include<cstring>
   
4. #include<map>
   
5. using namespace std;
   
6. const int dx[]={-1,0,1,0};
   
7. const int dy[]={0,1,0,-1};
   
8. int st;
   
9. int a[5][5];
   
10. int px,py;//0的位置
    
11. queue<int>  q;
    
12. map<int,int> d;
    
13. map<int,bool> v;
    
14. void unzip(int ret)
    
15. {
    
16.     for(int i=3;i>=1;i--)
    
17.         for(int j=3;j>=1;j--)
    
18.     {
    
19.         a[i][j]=ret%10;
    
20.         ret/=10;
    
21.         if(a[i][j]==0)
    
22.         {
    
23.             px=i;
    
24.             py=j;
    
25.         }
    
26.     }
    
27. }
    
28. int hsh()
    
29. {
    
30.     int ret=0;
    
31.     for(int i=1;i<=3;i++)
    
32.         for(int j=1;j<=3;j++)
    
33.         ret=ret*10+a[i][j];
    
34.     return ret;
    
35. }
    
36. int main()
    
37. {
    
38.     cin>>st;
    
39.     q.push(st);
    
40.     d[st]=0;
    
41.     while(!q.empty())
    
42.     {
    
43.         int x=q.front();
    
44.         q.pop();
    
45.         if(x==123804765) {cout<<d[x];return 0;}
    
46.         if(v[x]) continue;
    
47.         v[x]=1;
    
48.         unzip(x);
    
49.         for(int i=0;i<=3;i++)
    
50.             if(px+dx[i]>0&&px+dx[i]<=3&&py+dy[i]>0&&py+dy[i]<=3)
    
51.         {
    
52.             swap(a[px][py],a[px+dx[i]][py+dy[i]]);
    
53.             q.push(hsh());
    
54.             d[hsh()]=d[x]+1;
    
55.             swap(a[px][py],a[px+dx[i]][py+dy[i]]);
    
56.         }
    
57.     }
    
58.     return 0;
    
59. }
    

复制代码

张笑宇

为什么RE？？？

1. #include<iostream>
   
2. using namespace std;
   
3. string s;
   
4. int i,j,l,head,tail,temp;
   
5. const int mx=100010;
   
6. const int mm=4;
   
7. int dx[mx],dy[mx],d[mx];
   
8. int a[mm][mm][mx];
   
9. int fx[5]= {0,-1,0,0,+1};
   
10. int fy[5]= {0,0,-1,+1,0};
    
11. int mymap[5][5]= {0,0,0,0,0,
    
12.                   0,1,2,3,0,
    
13.                   0,8,0,4,0,
    
14.                   0,7,6,5,0,
    
15.                   0,0,0,0,0
    
16.                  };
    
17. bool bb(int x)
    
18. {
    
19.     int k,v;
    
20.     for (k=1; k<=3; k++)
    
21.         for (v=1; v<=3; v++)
    
22.             if (a[k][v][x]!=mymap[k][v]) return false;
    
23.     return true;
    
24. }
    
25. void cc(int x)
    
26. {
    
27.     int k,v;
    
28.     for (k=1; k<=3; k++)
    
29.     {
    
30.         for (v=1; v<=3; v++)
    
31.             cout<<a[k][v][x]<<" ";
    
32.         cout<<endl;
    
33.     }
    
34.     cout<<endl;
    
35. }
    
36. int main()
    
37. {
    
38.     cin>>s;
    
39.     for (i=0; i<=2; i++)
    
40.         for (j=0; j<=2; j++)
    
41.         {
    
42.             a[i+1][j+1][1]=s[3*i+j]-'0';
    
43.             if (a[i+1][j+1][1]==0) dx[1]=i+1,dy[1]=j+1;
    
44.         }
    
45.     ///cc(1);
    
46.     head=1,tail=2,d[1]=0;
    
47.     while (head<=tail)
    
48.     {
    
49.         if (bb(head))
    
50.         {
    
51.             cout<<d[head];
    
52.             return 0;
    
53.         }
    
54.         int nowx=dx[head];
    
55.         int nowy=dy[head];///现在的空位
    
56.         for (i=1; i<=4; i++)
    
57.         {
    
58.             int tx=nowx+fx[i];
    
59.             int ty=nowy+fy[i];///移动的位置
    
60.             if (1<=tx&&tx<=3&&1<=ty&&ty<=3)///如果可以
    
61.             {
    
62.                 for (j=1; j<=3; j++)
    
63.                     for (l=1; l<=3; l++)
    
64.                         a[j][l][tail]=a[j][l][head];
    
65.                 a[nowx][nowy][tail]=a[tx][ty][head];
    
66.                 a[tx][ty][tail]=0;///空位
    
67.                 dx[tail]=tx;
    
68.                 dy[tail]=ty;
    
69.                 d[tail]=d[head]+1;///cc(tail);
    
70.                 tail++;
    
71.             }
    
72.         }
    
73.         head++;
    
74.     }
    
75.     return 0;
    
76. }
    

复制代码