【数据结构】递归求解迷宫问题

前端之家收集整理的这篇文章主要介绍了【数据结构】递归求解迷宫问题前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

数据结构 递归求解迷宫问题

参考代码如下:
  1. /*
  2. 名称:递归求解迷宫问题
  3. 编译环境:VC++ 6.0
  4. 日期: 2014年4月1日
  5. */
  6. #include<stdio.h>
  7. #include<windows.h>
  8. // 迷宫坐标位置类型
  9. struct PosType
  10. {
  11. int x; // 行值
  12. int y; // 列值
  13. };
  14.  
  15. #define MAXLENGTH 25 // 设迷宫的最大行列为25
  16. typedef int MazeType[MAXLENGTH][MAXLENGTH]; // [行][列]
  17.  
  18. // 全局变量
  19. struct PosType end; // 迷宫终点位置
  20. MazeType m; // 迷宫数组
  21. int x,y; // 迷宫行数,列数
  22.  
  23. // 定义墙元素值为0,可通过路径为-1,通过路径为足迹
  24.  
  25. // 输出
  26. void Print(int x,int y)
  27. {
  28. int i,j;
  29. for(i=0;i<x;i++)
  30. {
  31. for(j=0;j<y;j++)
  32. printf("%3d",m[i][j]);
  33. printf("\n");
  34. }
  35. printf("\n");
  36. }
  37.  
  38. // 由当前位置cur、当前步骤curstep试探下一点
  39. void Try(struct PosType cur,int curstep)
  40. {
  41. int i;
  42. struct PosType next; // 下一个位置
  43. // {行增量,列增量}
  44. struct PosType direc[4]={{0,1},{1,0},{0,-1},{-1,0}};
  45. // 移动方向,依次为东南西北
  46. for(i=0;i<=3;i++) // 依次试探东南西北四个方向
  47. {
  48. next.x=cur.x+direc[i].x;
  49. next.y=cur.y+direc[i].y;
  50.  
  51. if(m[next.x][next.y] == -1) // 是通路
  52. {
  53. m[next.x][next.y]=++curstep;
  54. if(next.x != end.x || next.y != end.y) // 没到终点
  55. Try(next,curstep); // 试探下一点(递归调用)
  56. else
  57. Print(x,y); // 输出结果
  58. m[next.x][next.y]=-1; // 恢复为通路,试探下一条路
  59. curstep--;
  60. }
  61. }
  62. }
  63.  
  64. // 0为墙,-1为通道
  65.  
  66. int main()
  67. {
  68. struct PosType begin; //起点
  69. int i,j,x1,y1;
  70.  
  71. printf("请输入迷宫的行数,列数(包括外墙):(空格隔开)");
  72. scanf("%d%d",&x,&y);
  73. for(i=0;i<x;i++) // 定义周边值为0(同墙)
  74. {
  75. m[0][i]=0; // 迷宫上面行的周边即上边墙
  76. m[x-1][i]=0;// 迷宫下面行的周边即下边墙
  77. }
  78. for(j=1;j<y-1;j++)
  79. {
  80. m[j][0]=0; // 迷宫左边列的周边即左边墙
  81. m[j][y-1]=0;// 迷宫右边列的周边即右边墙
  82. }
  83. for(i=1;i<x-1;i++)
  84. for(j=1;j<y-1;j++)
  85. m[i][j]=-1; // 定义通道初值为-1
  86. printf("请输入迷宫内墙单元数(即墙的个数):");
  87. scanf("%d",&j);
  88. if(j)
  89. printf("请依次输入迷宫内墙每个单元的行数,列数:(空格隔开)\n");
  90. for(i=1;i<=j;i++)
  91. {
  92. scanf("%d%d",&x1,&y1);
  93. m[x1][y1]=0;
  94. }
  95. printf("迷宫结构如下:\n");
  96. Print(x,y);
  97. printf("请输入起点的行数,列数:(空格隔开)");
  98. scanf("%d%d",&begin.x,&begin.y);
  99. printf("请输入终点的行数,&end.x,&end.y);
  100. m[begin.x][begin.y]=1;
  101. Try(begin,1); // 由第一步起点试探起
  102. system("pause");
  103. return 0;
  104. }
  105.  
  106. /*
  107. 输出效果
  108.  
  109. 请输入迷宫的行数,列数(包括外墙):(空格隔开)4 4
  110. 请输入迷宫内墙单元数(即墙的个数):1
  111. 请依次输入迷宫内墙每个单元的行数,列数:(空格隔开)
  112. 1 2
  113. 迷宫结构如下:
  114. 0 0 0 0
  115. 0 -1 0 0
  116. 0 -1 -1 0
  117. 0 0 0 0
  118.  
  119. 请输入起点的行数,列数:(空格隔开)1 1
  120. 请输入终点的行数,列数:(空格隔开)2 2
  121. 0 0 0 0
  122. 0 1 0 0
  123. 0 2 3 0
  124. 0 0 0 0
  125.  
  126. 请按任意键继续. . .
  127.  
  128. */

运行结果如下:

猜你在找的数据结构相关文章