[关闭]
@jtahstu 2017-09-15T02:06:46.000000Z 字数 2492 阅读 269

迷宫求解(深搜和广搜)

算法


本文主要来源《啊哈!算法》第4章第2、3节

需要解决的问题

一个迷宫,由n行m列的单元格组成(0 < n,m <= 50),每个空格要么为障碍物,要么为空格,求一条从迷宫起点(1,1)到目标地点(小哈的位置)的最短路径。

分析

深搜

规定一个搜索顺序(右下左上),一直走下去。如果没有到达,继续枚举四个方向搜索;如果超过迷宫边界还没到达,则该次递归结束;如果到达小哈的位置,则停止改点的下次搜索,这时候比较最小值,存下来。最后输出最小值。

广搜

通过起点去向下一个位置探索,将下一步可以到达的位置加入队列,并标记已经走过。然后从队列中依次取点,再向下一步可以到达的位置探索,再加入队列,直到到达小哈的位置为止。

代码

dfs

  1. //
  2. // main.cpp
  3. // Maze_dfs
  4. //
  5. // Created by jtusta on 2017/6/19.
  6. // Copyright © 2017年 jtahstu. All rights reserved.
  7. //
  8. #include <iostream>
  9. #include <cstdio>
  10. using namespace std;
  11. int n,m,p,q,minx=999999;
  12. int a[51][51],book[51][51];
  13. void dfs(int x,int y,int step){
  14. int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
  15. int tx,ty,k;
  16. if(x==p && y==q){ //判断是否到达小哈的位置
  17. if(step<minx)
  18. minx=step;
  19. return;
  20. }
  21. for(k=0;k<4;k++){ //向四个方向枚举
  22. tx=x+next[k][0];
  23. ty=y+next[k][1];
  24. if(tx<1 || tx>n || ty<1 || ty>m) //判断是否越界
  25. continue;
  26. if(a[tx][ty]==0 && book[tx][ty]==0){
  27. book[tx][ty]=1; //标记这个点已经走过
  28. dfs(tx,ty,step+1); //开始尝试下一个点
  29. book[tx][ty]=0; //尝试结束,取消这个点标记
  30. }
  31. }
  32. return;
  33. }
  34. int main() {
  35. int i,j,startx,starty;
  36. cin>>n>>m; //n行m列的迷宫
  37. for(i=1;i<=n;i++) //读入迷宫
  38. for(j=1;j<=m;j++)
  39. cin>>a[i][j];
  40. cin>>startx>>starty>>p>>q;
  41. book[startx][starty]=1; //标记起点,防止后面重复走==
  42. dfs(startx,starty,0);
  43. cout<<minx<<endl; //
  44. return 0;
  45. }
  46. /*
  47. * 测试数据
  48. 5 4
  49. 0 0 1 0
  50. 0 0 0 0
  51. 0 0 1 0
  52. 0 1 0 0
  53. 0 0 0 1
  54. 1 1 4 3
  55. */
  1. 5 4
  2. 0 0 1 0
  3. 0 0 0 0
  4. 0 0 1 0
  5. 0 1 0 0
  6. 0 0 0 1
  7. 1 1 4 3
  8. 7
  9. Program ended with exit code: 0

bfs

  1. //
  2. // main.cpp
  3. // Maze_bfs
  4. //
  5. // Created by jtusta on 2017/6/19.
  6. // Copyright © 2017年 jtahstu. All rights reserved.
  7. //
  8. #include <iostream>
  9. #include <cstdio>
  10. using namespace std;
  11. struct note
  12. {
  13. int x,y,f,s; //横纵坐标、父亲在队列中的编号、步数
  14. //父亲在队列中的编号,本体不要求输出路径,可以不需要f
  15. };
  16. int main() {
  17. struct note que[2501];
  18. int a[51][51]={0},book[51][51]={0};
  19. int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; //向四个方向走的数组
  20. int head,tail;
  21. int i,j,k,n,m,startx,starty,p,q,tx,ty,flag;
  22. cin>>n>>m;
  23. for(i=1;i<=n;i++)
  24. for(j=1;j<=m;j++)
  25. cin>>a[i][j];
  26. cin>>startx>>starty>>p>>q;
  27. head=1; //队列初始化
  28. tail=1;
  29. que[tail].x=startx; //往队列插入迷宫入口坐标
  30. que[tail].y=starty;
  31. que[tail].f=0;
  32. que[tail].s=0;
  33. tail++;
  34. book[startx][starty]=1;
  35. flag=0;
  36. while(head<tail){
  37. for(k=0;k<4;k++){ //枚举四个方向
  38. tx=que[head].x+next[k][0];
  39. ty=que[head].y+next[k][1];
  40. if(tx<1 || tx>n || ty<0 || ty>m) //是否越界
  41. continue;
  42. //判断是否为障碍物 或者已经在路径中
  43. if(a[tx][ty]==0 && book[tx][ty]==0){
  44. book[tx][ty]=1; //把这个点标记为走过,注意宽搜每个点只入列一次,所以和深搜不同,不需要将book数组还原
  45. //插入新的点到队列中
  46. que[tail].x=tx;
  47. que[tail].y=ty;
  48. que[tail].f=head; //因为这个点是从head拓展而来,所以它的父亲是head,本题目不需要求路径,因此本句可以省略
  49. que[tail].s=que[head].s+1;
  50. tail++;
  51. }
  52. if(tx==p&&ty==q){
  53. flag=1;
  54. break;
  55. }
  56. }
  57. if(flag==1)
  58. break;
  59. head++; //此地方不能忘记,当一个点拓展结束,head++才能对后面的点再进行拓展
  60. }
  61. //打印队列中末尾最后一个点(目标点)的步数
  62. //注意tail是指向队列队尾(即最后一位)的下一个位置,所以这需要-1
  63. cout<<que[tail-1].s<<endl;
  64. return 0;
  65. }
  66. /*
  67. 测试数据
  68. 5 4
  69. 0 0 1 0
  70. 0 0 0 0
  71. 0 0 1 0
  72. 0 1 0 0
  73. 0 0 0 1
  74. 1 1 4 3
  75. */
  1. 5 4
  2. 0 0 1 0
  3. 0 0 0 0
  4. 0 0 1 0
  5. 0 1 0 0
  6. 0 0 0 1
  7. 1 1 4 3
  8. 7
  9. Program ended with exit code: 0
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注