bfs来搜索目标局面,一旦搜到一定是最小移动次数
任务:
  1. 目标检查
  2. 判重
通常利用哈希表记录每一种不同的局面
  1. typedef int State[9];//哈希映射
  2. State st[Maxsize],goal;//st二维数组存储每种情形,goal数组存储目标数组
  3. int hash(State& s)
  4. {
  5. int v = 0;
  6. for(int i=0; i<9; i++) v = v*10 + s[i]; //把9个数字组合成9位数
  7. return v % Maxsize; //确保hash函数值是不超过hash表的大小的非负整数
  8. }
复习一下三个函数
  1. memcpy(&t ,&s ,sizeof(s));//从源source所指的内存地址的起始位置开始拷贝n个字节到目标destin所指的内存地址的起始位置中。
  2. if(memcmp(st[s], st[u], sizeof(st[s]))==0) return 0; //把存储区str1和存储区str2的前n个字节进行比较
  3. memset(head, 0, sizeof(head));//为新申请的内存做初始化工作。
插入链表的实现
  1. int try_to_insert(int s)
  2. {
  3. int h = hash(st[s]);
  4. int u = head[h]; //从表头开始查找链表
  5. while(u){//把存储区str1和存储区str2的前n个字节进行比较
  6. if(memcmp(st[s], st[u], sizeof(st[s]))==0) return 0; //有重复,插入失败
  7. u = next[u]; //顺着链表继续找
  8. }
  9. next[s] = head[h]; //该结点插入到链表中
  10. head[h] = s;
  11. return 1;
  12. }
核心bfs实现
  1. int bfs()
  2. {
  3. init_table();
  4. int front=1,rear=2;
  5. while(front<rear)
  6. {
  7. State &s=st[front];int z;
  8. if(memcmp(goal,s,sizeof(s))==0) return front;
  9. for(int i=0;i<9;i++)
  10. {
  11. if(!s[i]) z=i;
  12. }
  13. int x=z/3,y=z%3;
  14. for(int i=0;i<4;i++)
  15. {
  16. int newx=x+dx[i];
  17. int newy=y+dy[i];
  18. int newz=3*newx+newy;
  19. if(newx<3&&newx>=0&&newy<3&&newy>=0)
  20. {
  21. State &t=st[rear];
  22. memcpy(&t,&s,sizeof(s));
  23. t[newz]=s[z];
  24. t[z]=s[newz];
  25. dist[rear]=dist[front]+1;
  26. if(try_to_insert(rear)) rear++;
  27. }
  28. }
  29. front++;
  30. }
  31. return 0;
  32. }

完整参考代码

  1. #include<iostream>
  2. #include<cstring>
  3. using namespace std;
  4. const int Maxsize=1000000;
  5. string str1,str2;
  6. int dist[Maxsize];
  7. int dx[4]={0,0,1,-1};
  8. int dy[4]={1,-1,0,0};
  9. typedef int State[9];
  10. State st[Maxsize],goal;
  11. int head[Maxsize],next1[Maxsize];
  12. void init_table()
  13. {
  14. memset(head,0,sizeof(head));
  15. }
  16. int hash1(State &s)
  17. {
  18. int sum=0;
  19. for(int i=0;i<9;i++)
  20. {
  21. sum=sum*10+s[i];
  22. }
  23. return sum%Maxsize;
  24. }
  25. int try_to_insert(int s)
  26. {
  27. int h=hash1(st[s]);
  28. int u=head[h];
  29. while(u)
  30. {
  31. if(memcmp(st[s],st[u],sizeof(st[s]))==0)
  32. return 0;
  33. u=next1[u];
  34. }
  35. next1[s]=head[h];
  36. head[h]=s;
  37. return 1;
  38. }
  39. int bfs()
  40. {
  41. init_table();
  42. int front=1,rear=2;
  43. while(front<rear)
  44. {
  45. State &s=st[front];int z;
  46. if(memcmp(goal,s,sizeof(s))==0) return front;
  47. for(int i=0;i<9;i++)
  48. {
  49. if(!s[i]) z=i;
  50. }
  51. int x=z/3,y=z%3;
  52. for(int i=0;i<4;i++)
  53. {
  54. int newx=x+dx[i];
  55. int newy=y+dy[i];
  56. int newz=3*newx+newy;
  57. if(newx<3&&newx>=0&&newy<3&&newy>=0)
  58. {
  59. State &t=st[rear];
  60. memcpy(&t,&s,sizeof(s));
  61. t[newz]=s[z];
  62. t[z]=s[newz];
  63. dist[rear]=dist[front]+1;
  64. if(try_to_insert(rear)) rear++;
  65. }
  66. }
  67. front++;
  68. }
  69. return 0;
  70. }
  71. int main()
  72. {
  73. cin>>str1>>str2;
  74. for(int i=0; i<9; i++) {
  75. if(str1[i]=='.')
  76. st[1][i] = 0;
  77. else
  78. st[1][i] = str1[i] - '0';
  79. }
  80. for(int i=0; i<9; i++){
  81. if(str2[i]=='.')
  82. goal[i] = 0;
  83. else
  84. goal[i] = str2[i] - '0';
  85. }
  86. int ans = bfs();
  87. if(ans == 0) printf("%d\n",-1);
  88. else
  89. printf("%d\n",dist[ans]);
  90. return 0;
  91. }
点赞(0)
 

4.4 分

3 人评分

 

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 0 条评论

暂无评论