首页 > 其他 > 详细

洛谷 P1379 八数码难题 题解

时间:2019-07-24 14:06:38      阅读:85      评论:0      收藏:0      [点我收藏+]

我个人感觉就是一道bfs的变形,还是对bfs掌握不好的人有一定难度。

本题思路:

大体上用bfs搜,用map来去重,在这里只需要一个队列,因为需要较少步数达到的状态一定在步数较多的状态之前入队列。

 1 #include<iostream>
 2 #include<cmath>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<map>
 6 #include<queue>
 7 using namespace std;
 8 long long dx[4]={-1,0,0,1};
 9 long long dy[4]={0,-1,1,0};
10 long long n;
11 int  main()
12 {
13     cin>>n;
14     queue<long long> q;
15     q.push(n);
16     map<long long,long long> m;
17     m[n]=0;
18     while(!q.empty())
19     {
20         int cnt=q.front(); 
21         int zyc[3][3],xx=0,yy=0,n=cnt;
22         q.pop();
23         if(cnt==123804765)break;
24         for(long long i=2;i>=0;i--)
25             for(long long j=2;j>=0;j--)
26             {
27                 zyc[i][j]=n%10;
28                 n/=10;
29                 if(!zyc[i][j])
30                 {
31                     xx=i;
32                     yy=j;
33                 }
34             }
35         for(long long i=0;i<4;i++)
36         {
37             long long nx=xx+dx[i],ny=yy+dy[i],ans=0;
38             if(nx<0||ny<0||nx>2||ny>2)continue;
39             swap(zyc[nx][ny],zyc[xx][yy]);
40             for(long long i=0;i<3;i++)
41                 for(long long j=0;j<3;j++)ans=ans*10+zyc[i][j];
42             if(!m.count(ans))
43             {
44                 m[ans]=m[cnt]+1;
45                 q.push(ans);
46             }
47             swap(zyc[nx][ny],zyc[xx][yy]);
48         }
49     }
50     cout<<m[123804765]; 
51     return 0;
52 }
请各位大佬斧正(反正我不认识斧正是什么意思)

 

洛谷 P1379 八数码难题 题解

原文:https://www.cnblogs.com/handsome-zyc/p/11237371.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!