您的位置: 首页  >  文章  >  生成迷宫的深度优先遍历算法的非递归实现

生成迷宫的深度优先遍历算法的非递归实现

分类: 文章 • 2024-12-28 21:27:28

一.算法分析：

生成一张二维单路径迷宫图，可以想到的方法之一就是图的遍历。因为单路径顾名思义就是要求每个节点能切只能访问一次，这正好和图的遍历方法一样。其次就是图的遍历保证了只有一条路径。

运行后即如下图所示：

生成迷宫的深度优先遍历算法的非递归实现

①首先创建一个二维数组，char maze[H][W]，其中H和W必须是奇数，创建一个空间足够大的栈stack[H*W]；

②初始化maze将四周存入‘w’(表示墙的意思)，中间的存入‘n'（表示还未被访问的意思，中间的数组共有三种状态’n'，‘y'：已经被访问，’r'：将要被访问）

③开始从maze[1][1]进行循环，首先判断可以访问的方向，然后随机产生一个方向，进行入栈，如果没有可以访问的方向则开始出栈，直到栈为空，跳出循环。

生成迷宫的深度优先遍历算法的非递归实现

生成迷宫的深度优先遍历算法的非递归实现生成迷宫的深度优先遍历算法的非递归实现

二.C语言实现（附加走迷宫函数path()）

[cpp] view plain copy
  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3. #include <windows.h>  
  4. #include <time.h>  
  5. #define H 11//高  
  6. #define W 11//宽  
  7. #define MAX 121//栈的深度H和W的乘积  
  8. typedef struct path {  
  9.     COORD cell;  
  10.     struct path *pro;  
  11.     struct path *next;  
  12. }PATH;  
  13.   
  14. void inimaze(char maze[H][W])//初始化函数  
  15. {  
  16.     int i, j;//i高度j宽度  
  17.     for (i = 1; i<H; i++)  
  18.     {  
  19.         for (j = 1; j<W - 1; j++)  
  20.         {  
  21.             maze[i][j] = 'n';//n表示没有被访问y表示已被访问r表示准备访问w表示墙  
  22.         }  
  23.     }  
  24.     //设置墙  
  25.     for (i = 0; i<H; i++)  
  26.     {  
  27.         maze[i][0] = 'w';  
  28.         maze[i][W - 1] = 'w';  
  29.     }  
  30.     for (j = 0; j<W; j++)  
  31.     {  
  32.         maze[0][j] = 'w';  
  33.         maze[H - 1][j] = 'w';  
  34.     }  
  35. }  
  36. void creatmaze(char maze[H][W])//生成迷宫的函数  
  37. {  
  38.     srand(time(NULL));  
  39.     COORD stack[MAX];  
  40.     int head = -1;  
  41.     //需要的工具栈  
  42.   
  43.     int i = 1, j = 1;  
  44.   
  45.     //当前坐标  
  46.     head++;  
  47.     stack[head].X = i;  
  48.     stack[head].Y = j;  
  49.     maze[i][j] = 'y';  
  50.     //进入循环前的准备  
  51.   
  52.     char dir[4], c;//用于存放有几个方向可以访问  
  53.     int k, m, t;//k用于初始化dir[],m+1是方向的个数，  
  54.     for (k = 0; k <= 3; k++)  
  55.     {  
  56.         dir[k] = '\0';//u d l r  
  57.     }  
  58.   
  59.     while (head != -1)//while中有四个模块分别对应的①判断有多少个方向可以访问 ②随机访问一个方向 ③当没有访问的方向后开始退栈  
  60.     {  
  61.         m = -1;  
  62.         if ((maze[i+1][j]!='w' && maze[i + 2][j] == 'n') || maze[i + 2][j] == 'r')  
  63.         {  
  64.             maze[i + 2][j] = 'r';  
  65.             m++;  
  66.             dir[m] = 'd';  
  67.         }  
  68.         if ((maze[i-1][j]!='w' && maze[i - 2][j] == 'n') || maze[i - 2][j] == 'r')  
  69.         {  
  70.             maze[i - 2][j] = 'r';  
  71.             m++;  
  72.             dir[m] = 'u';  
  73.         }  
  74.         if ((maze[i][j+1]!='w' && maze[i][j + 2] == 'n') || maze[i][j + 2] == 'r')  
  75.         {  
  76.             maze[i][j + 2] = 'r';  
  77.             m++;  
  78.             dir[m] = 'r';  
  79.         }  
  80.         if ((maze[i][j-1]!='w' && maze[i][j - 2] == 'n') || maze[i][j - 2] == 'r')  
  81.         {  
  82.             maze[i][j - 2] = 'r';  
  83.             m++;  
  84.             dir[m] = 'l';  
  85.         }  
  86.         //以上四个if语句得出两个结果m：可以走的方向个数，dir[]:具体的可走的方向  
  87.         if (m >= 0)  
  88.         {  
  89.             t = rand() % (m + 1);//随机的方向  
  90.             c = dir[t];  
  91.             switch (c)  
  92.             {  
  93.             case 'u':  
  94.                 maze[i - 1][j] = 'y';  
  95.                 i -= 2;  
  96.                 maze[i][j] = 'y';  
  97.                 break;  
  98.             case 'd':  
  99.                 maze[i + 1][j] = 'y';  
  100.                 i += 2;  
  101.                 maze[i][j] = 'y';  
  102.                 break;  
  103.             case 'r':  
  104.                 maze[i][j + 1] = 'y';  
  105.                 j += 2;  
  106.                 maze[i][j] = 'y';  
  107.                 break;  
  108.             case 'l':  
  109.                 maze[i][j - 1] = 'y';  
  110.                 j -= 2;  
  111.                 maze[i][j] = 'y';  
  112.                 break;  
  113.             }  
  114.             head++;  
  115.             stack[head].X = i;  
  116.             stack[head].Y = j;  
  117.   
  118.         }  
  119.         //这一个if语句目的是随机访问下一个节点  
  120.         if (m == -1)  
  121.         {  
  122.             head--;  
  123.             i = stack[head].X;  
  124.             j = stack[head].Y;  
  125.   
  126.         }  
  127.         //如果m=-1；说明走投无路开始退栈  
  128.   
  129.     }  
  130.   
  131.   
  132.   
  133. }  
  134. void print_maze(char maze[H][W])  
  135. {  
  136.     int i, j;  
  137.     char c;  
  138.     for (i = 0; i<H; i++)  
  139.     {  
  140.         for (j = 0; j<W; j++)  
  141.         {  
  142.             c = maze[i][j];  
  143.             if (c == 'y')  
  144.             {  
  145.                 printf("  ");  
  146.             }  
  147.             else  
  148.             {  
  149.                 printf("█");  
  150.             }  
  151.         }  
  152.         printf("\n");  
  153.     }  
  154.     printf("\n\n");  
  155. }  
  156. void print_maze2(char maze[H][W])//此函数纯属调试的时候看二维数组中的状态  
  157. {  
  158.     int i, j;  
  159.     char c;  
  160.     for (i = 0; i<H; i++)  
  161.     {  
  162.         for (j = 0; j<W; j++)  
  163.         {  
  164.             c = maze[i][j];  
  165.             if (c == 'y')  
  166.             {  
  167.                 printf("%c", c);  
  168.             }  
  169.             else  
  170.             {  
  171.                 printf("%c", c);  
  172.             }  
  173.         }  
  174.         printf("\n");  
  175.     }  
  176.     printf("\n\n");  
  177. }  
  178. void putout_file(char maze[H][W])  
  179. {  
  180.     int i, j,ch;  
  181.     FILE *fp;  
  182.     if ((fp=fopen("maze.data", "a+")) == NULL)  
  183.     {  
  184.         fp=fopen("maze.data", "w+");  
  185.     }  
  186.     for (i = 0; i < H; i++ )  
  187.     {  
  188.         for (j = 0; j < W; j++ )  
  189.         {  
  190.             if (maze[i][j] == 'y')  
  191.             {  
  192.                 ch = 'O';  
  193.             }  
  194.             else  
  195.             {  
  196.                 ch = '*';  
  197.             }  
  198.             putc(ch, fp);  
  199.         }  
  200.         putc('\n', fp);  
  201.     }  
  202.     putc('\n\n\n', fp);  
  203.     fclose(fp);  
  204. }  
  205.   
  206. void path(char maze[H][W],PATH *head)//*********此函数会破坏迷宫数组将其中的y用Y代替**********此函数在最后使用  
  207. {  
  208.     head = (PATH *)malloc(sizeof(PATH));  
  209.     PATH *p = head;  
  210.     //初始化  
  211.     head->cell.X = 1;  
  212.     head->cell.Y = 1;  
  213.     head->pro = NULL;  
  214.     head->next = NULL;  
  215.     //存储方向的数组  
  216.     int m;  
  217.     char dir[4],ch;  
  218.     maze[1][1] = 'Y';  
  219.     while ((p->cell.X != H - 2) || (p->cell.Y != W - 2))  
  220.     {  
  221.         for (m = 0; m < 4; m++)  
  222.         {  
  223.             dir[m] = '\0';  
  224.         }  
  225.         m = -1;  
  226.         if (maze[p->cell.X - 1][p->cell.Y] == 'y')  
  227.         {  
  228.             m++;  
  229.             dir[m] = 'u';  
  230.         }  
  231.         if (maze[p->cell.X + 1][p->cell.Y] == 'y')  
  232.         {  
  233.             m++;  
  234.             dir[m] = 'd';  
  235.         }  
  236.         if (maze[p->cell.X][p->cell.Y - 1]=='y')  
  237.         {  
  238.             m++;  
  239.             dir[m] = 'l';  
  240.         }  
  241.         if (maze[p->cell.X][p->cell.Y+1] == 'y')  
  242.         {  
  243.             m++;  
  244.             dir[m] = 'r';  
  245.         }  
  246.           
  247.         //判断可走的方向  
  248.         if (m >= 0)  
  249.         {  
  250.             p->next = (PATH *)malloc(sizeof(PATH));  
  251.             p->next->cell.X = p->cell.X;  
  252.             p->next->cell.Y = p->cell.Y;  
  253.             p->next->pro = p;  
  254.             p->next->next = NULL;  
  255.             //把当前位置继承下来并且初始化next  
  256.             p = p->next;  
  257.             srand(time(NULL));  
  258.             ch = dir[rand() % (m + 1)];  
  259.             switch (ch)  
  260.             {  
  261.             case 'u':  
  262.                 p->cell.X -= 1;  
  263.                 maze[p->cell.X][p->cell.Y] = 'Y';  
  264.                 break;  
  265.             case 'd':  
  266.                 p->cell.X += 1;  
  267.                 maze[p->cell.X][p->cell.Y] = 'Y';  
  268.                 break;  
  269.             case 'l':  
  270.                 p->cell.Y -= 1;  
  271.                 maze[p->cell.X][p->cell.Y] = 'Y';  
  272.                 break;  
  273.             case 'r':  
  274.                 p->cell.Y += 1;  
  275.                 maze[p->cell.X][p->cell.Y] = 'Y';  
  276.                 break;  
  277.             }  
  278.         }  
  279.         else  
  280.         {  
  281. //          maze[p->cell.X][p->cell.Y] = 'y';  
  282.             p = p->pro;  
  283.             free(p->next);  
  284.             p->next = NULL;  
  285.         }  
  286.     }  
  287.     p = head;  
  288.     while (p != NULL)  
  289.     {  
  290.         printf("(%d,%d)",p->cell.X,p->cell.Y);  
  291.         p = p->next;  
  292.     }  
  293.     printf("\n");  
  294. }  
  295. int main()  
  296. {  
  297.     char maze[H][W];  
  298.     PATH *head = NULL;  
  299.     inimaze(maze);  
  300.     creatmaze(maze);  
  301.     print_maze(maze);  
  302.     putout_file(maze);  
  303.     path(maze, head);  
  304.     print_maze2(maze);  
  305.     Sleep(5000);  
  306.     return 0;  
  307.   
  308. }  


[cpp] view plain copy
  1. <span style="font-family:Arial, Helvetica, sans-serif;"><span style="white-space:normal;"></span></span>  








 
一.算法分析：


生成一张二维单路径迷宫图，可以想到的方法之一就是图的遍历。因为单路径顾名思义就是要求每个节点能切只能访问一次，这正好和图的遍历方法一样。其次就是图的遍历保证了只有一条路径。


运行后即如下图所示：


生成迷宫的深度优先遍历算法的非递归实现


①首先创建一个二维数组，char maze[H][W]，其中H和W必须是奇数，创建一个空间足够大的栈stack[H*W]；


②初始化maze将四周存入‘w’(表示墙的意思)，中间的存入‘n'（表示还未被访问的意思，中间的数组共有三种状态’n'，‘y'：已经被访问，’r'：将要被访问）


③开始从maze[1][1]进行循环，首先判断可以访问的方向，然后随机产生一个方向，进行入栈，如果没有可以访问的方向则开始出栈，直到栈为空，跳出循环。


生成迷宫的深度优先遍历算法的非递归实现


生成迷宫的深度优先遍历算法的非递归实现生成迷宫的深度优先遍历算法的非递归实现



二.C语言实现（附加走迷宫函数path()）







[cpp] view plain copy







    

  1. #include <stdio.h>  
    2. 

  2. #include <stdlib.h>  
    3. 

  3. #include <windows.h>  
    4. 

  4. #include <time.h>  
    5. 

  5. #define H 11//高  
    6. 

  6. #define W 11//宽  
    7. 

  7. #define MAX 121//栈的深度H和W的乘积  
    8. 

  8. typedef struct path {  
    9. 

  9.     COORD cell;  
    10. 

  10.     struct path *pro;  
    11. 

  11.     struct path *next;  
    12. 

  12. }PATH;  
    13. 

  13.   
    14. 

  14. void inimaze(char maze[H][W])//初始化函数  
    15. 

  15. {  
    16. 

  16.     int i, j;//i高度j宽度  
    17. 

  17.     for (i = 1; i<H; i++)  
    18. 

  18.     {  
    19. 

  19.         for (j = 1; j<W - 1; j++)  
    20. 

  20.         {  
    21. 

  21.             maze[i][j] = 'n';//n表示没有被访问y表示已被访问r表示准备访问w表示墙  
    22. 

  22.         }  
    23. 

  23.     }  
    24. 

  24.     //设置墙  
    25. 

  25.     for (i = 0; i<H; i++)  
    26. 

  26.     {  
    27. 

  27.         maze[i][0] = 'w';  
    28. 

  28.         maze[i][W - 1] = 'w';  
    29. 

  29.     }  
    30. 

  30.     for (j = 0; j<W; j++)  
    31. 

  31.     {  
    32. 

  32.         maze[0][j] = 'w';  
    33. 

  33.         maze[H - 1][j] = 'w';  
    34. 

  34.     }  
    35. 

  35. }  
    36. 

  36. void creatmaze(char maze[H][W])//生成迷宫的函数  
    37. 

  37. {  
    38. 

  38.     srand(time(NULL));  
    39. 

  39.     COORD stack[MAX];  
    40. 

  40.     int head = -1;  
    41. 

  41.     //需要的工具栈  
    42. 

  42.   
    43. 

  43.     int i = 1, j = 1;  
    44. 

  44.   
    45. 

  45.     //当前坐标  
    46. 

  46.     head++;  
    47. 

  47.     stack[head].X = i;  
    48. 

  48.     stack[head].Y = j;  
    49. 

  49.     maze[i][j] = 'y';  
    50. 

  50.     //进入循环前的准备  
    51. 

  51.   
    52. 

  52.     char dir[4], c;//用于存放有几个方向可以访问  
    53. 

  53.     int k, m, t;//k用于初始化dir[],m+1是方向的个数，  
    54. 

  54.     for (k = 0; k <= 3; k++)  
    55. 

  55.     {  
    56. 

  56.         dir[k] = '\0';//u d l r  
    57. 

  57.     }  
    58. 

  58.   
    59. 

  59.     while (head != -1)//while中有四个模块分别对应的①判断有多少个方向可以访问 ②随机访问一个方向 ③当没有访问的方向后开始退栈  
    60. 

  60.     {  
    61. 

  61.         m = -1;  
    62. 

  62.         if ((maze[i+1][j]!='w' && maze[i + 2][j] == 'n') || maze[i + 2][j] == 'r')  
    63. 

  63.         {  
    64. 

  64.             maze[i + 2][j] = 'r';  
    65. 

  65.             m++;  
    66. 

  66.             dir[m] = 'd';  
    67. 

  67.         }  
    68. 

  68.         if ((maze[i-1][j]!='w' && maze[i - 2][j] == 'n') || maze[i - 2][j] == 'r')  
    69. 

  69.         {  
    70. 

  70.             maze[i - 2][j] = 'r';  
    71. 

  71.             m++;  
    72. 

  72.             dir[m] = 'u';  
    73. 

  73.         }  
    74. 

  74.         if ((maze[i][j+1]!='w' && maze[i][j + 2] == 'n') || maze[i][j + 2] == 'r')  
    75. 

  75.         {  
    76. 

  76.             maze[i][j + 2] = 'r';  
    77. 

  77.             m++;  
    78. 

  78.             dir[m] = 'r';  
    79. 

  79.         }  
    80. 

  80.         if ((maze[i][j-1]!='w' && maze[i][j - 2] == 'n') || maze[i][j - 2] == 'r')  
    81. 

  81.         {  
    82. 

  82.             maze[i][j - 2] = 'r';  
    83. 

  83.             m++;  
    84. 

  84.             dir[m] = 'l';  
    85. 

  85.         }  
    86. 

  86.         //以上四个if语句得出两个结果m：可以走的方向个数，dir[]:具体的可走的方向  
    87. 

  87.         if (m >= 0)  
    88. 

  88.         {  
    89. 

  89.             t = rand() % (m + 1);//随机的方向  
    90. 

  90.             c = dir[t];  
    91. 

  91.             switch (c)  
    92. 

  92.             {  
    93. 

  93.             case 'u':  
    94. 

  94.                 maze[i - 1][j] = 'y';  
    95. 

  95.                 i -= 2;  
    96. 

  96.                 maze[i][j] = 'y';  
    97. 

  97.                 break;  
    98. 

  98.             case 'd':  
    99. 

  99.                 maze[i + 1][j] = 'y';  
    100. 

  100.                 i += 2;  
    101. 

  101.                 maze[i][j] = 'y';  
    102. 

  102.                 break;  
    103. 

  103.             case 'r':  
    104. 

  104.                 maze[i][j + 1] = 'y';  
    105. 

  105.                 j += 2;  
    106. 

  106.                 maze[i][j] = 'y';  
    107. 

  107.                 break;  
    108. 

  108.             case 'l':  
    109. 

  109.                 maze[i][j - 1] = 'y';  
    110. 

  110.                 j -= 2;  
    111. 

  111.                 maze[i][j] = 'y';  
    112. 

  112.                 break;  
    113. 

  113.             }  
    114. 

  114.             head++;  
    115. 

  115.             stack[head].X = i;  
    116. 

  116.             stack[head].Y = j;  
    117. 

  117.   
    118. 

  118.         }  
    119. 

  119.         //这一个if语句目的是随机访问下一个节点  
    120. 

  120.         if (m == -1)  
    121. 

  121.         {  
    122. 

  122.             head--;  
    123. 

  123.             i = stack[head].X;  
    124. 

  124.             j = stack[head].Y;  
    125. 

  125.   
    126. 

  126.         }  
    127. 

  127.         //如果m=-1；说明走投无路开始退栈  
    128. 

  128.   
    129. 

  129.     }  
    130. 

  130.   
    131. 

  131.   
    132. 

  132.   
    133. 

  133. }  
    134. 

  134. void print_maze(char maze[H][W])  
    135. 

  135. {  
    136. 

  136.     int i, j;  
    137. 

  137.     char c;  
    138. 

  138.     for (i = 0; i<H; i++)  
    139. 

  139.     {  
    140. 

  140.         for (j = 0; j<W; j++)  
    141. 

  141.         {  
    142. 

  142.             c = maze[i][j];  
    143. 

  143.             if (c == 'y')  
    144. 

  144.             {  
    145. 

  145.                 printf("  ");  
    146. 

  146.             }  
    147. 

  147.             else  
    148. 

  148.             {  
    149. 

  149.                 printf("█");  
    150. 

  150.             }  
    151. 

  151.         }  
    152. 

  152.         printf("\n");  
    153. 

  153.     }  
    154. 

  154.     printf("\n\n");  
    155. 

  155. }  
    156. 

  156. void print_maze2(char maze[H][W])//此函数纯属调试的时候看二维数组中的状态  
    157. 

  157. {  
    158. 

  158.     int i, j;  
    159. 

  159.     char c;  
    160. 

  160.     for (i = 0; i<H; i++)  
    161. 

  161.     {  
    162. 

  162.         for (j = 0; j<W; j++)  
    163. 

  163.         {  
    164. 

  164.             c = maze[i][j];  
    165. 

  165.             if (c == 'y')  
    166. 

  166.             {  
    167. 

  167.                 printf("%c", c);  
    168. 

  168.             }  
    169. 

  169.             else  
    170. 

  170.             {  
    171. 

  171.                 printf("%c", c);  
    172. 

  172.             }  
    173. 

  173.         }  
    174. 

  174.         printf("\n");  
    175. 

  175.     }  
    176. 

  176.     printf("\n\n");  
    177. 

  177. }  
    178. 

  178. void putout_file(char maze[H][W])  
    179. 

  179. {  
    180. 

  180.     int i, j,ch;  
    181. 

  181.     FILE *fp;  
    182. 

  182.     if ((fp=fopen("maze.data", "a+")) == NULL)  
    183. 

  183.     {  
    184. 

  184.         fp=fopen("maze.data", "w+");  
    185. 

  185.     }  
    186. 

  186.     for (i = 0; i < H; i++ )  
    187. 

  187.     {  
    188. 

  188.         for (j = 0; j < W; j++ )  
    189. 

  189.         {  
    190. 

  190.             if (maze[i][j] == 'y')  
    191. 

  191.             {  
    192. 

  192.                 ch = 'O';  
    193. 

  193.             }  
    194. 

  194.             else  
    195. 

  195.             {  
    196. 

  196.                 ch = '*';  
    197. 

  197.             }  
    198. 

  198.             putc(ch, fp);  
    199. 

  199.         }  
    200. 

  200.         putc('\n', fp);  
    201. 

  201.     }  
    202. 

  202.     putc('\n\n\n', fp);  
    203. 

  203.     fclose(fp);  
    204. 

  204. }  
    205. 

  205.   
    206. 

  206. void path(char maze[H][W],PATH *head)//*********此函数会破坏迷宫数组将其中的y用Y代替**********此函数在最后使用  
    207. 

  207. {  
    208. 

  208.     head = (PATH *)malloc(sizeof(PATH));  
    209. 

  209.     PATH *p = head;  
    210. 

  210.     //初始化  
    211. 

  211.     head->cell.X = 1;  
    212. 

  212.     head->cell.Y = 1;  
    213. 

  213.     head->pro = NULL;  
    214. 

  214.     head->next = NULL;  
    215. 

  215.     //存储方向的数组  
    216. 

  216.     int m;  
    217. 

  217.     char dir[4],ch;  
    218. 

  218.     maze[1][1] = 'Y';  
    219. 

  219.     while ((p->cell.X != H - 2) || (p->cell.Y != W - 2))  
    220. 

  220.     {  
    221. 

  221.         for (m = 0; m < 4; m++)  
    222. 

  222.         {  
    223. 

  223.             dir[m] = '\0';  
    224. 

  224.         }  
    225. 

  225.         m = -1;  
    226. 

  226.         if (maze[p->cell.X - 1][p->cell.Y] == 'y')  
    227. 

  227.         {  
    228. 

  228.             m++;  
    229. 

  229.             dir[m] = 'u';  
    230. 

  230.         }  
    231. 

  231.         if (maze[p->cell.X + 1][p->cell.Y] == 'y')  
    232. 

  232.         {  
    233. 

  233.             m++;  
    234. 

  234.             dir[m] = 'd';  
    235. 

  235.         }  
    236. 

  236.         if (maze[p->cell.X][p->cell.Y - 1]=='y')  
    237. 

  237.         {  
    238. 

  238.             m++;  
    239. 

  239.             dir[m] = 'l';  
    240. 

  240.         }  
    241. 

  241.         if (maze[p->cell.X][p->cell.Y+1] == 'y')  
    242. 

  242.         {  
    243. 

  243.             m++;  
    244. 

  244.             dir[m] = 'r';  
    245. 

  245.         }  
    246. 

  246.           
    247. 

  247.         //判断可走的方向  
    248. 

  248.         if (m >= 0)  
    249. 

  249.         {  
    250. 

  250.             p->next = (PATH *)malloc(sizeof(PATH));  
    251. 

  251.             p->next->cell.X = p->cell.X;  
    252. 

  252.             p->next->cell.Y = p->cell.Y;  
    253. 

  253.             p->next->pro = p;  
    254. 

  254.             p->next->next = NULL;  
    255. 

  255.             //把当前位置继承下来并且初始化next  
    256. 

  256.             p = p->next;  
    257. 

  257.             srand(time(NULL));  
    258. 

  258.             ch = dir[rand() % (m + 1)];  
    259. 

  259.             switch (ch)  
    260. 

  260.             {  
    261. 

  261.             case 'u':  
    262. 

  262.                 p->cell.X -= 1;  
    263. 

  263.                 maze[p->cell.X][p->cell.Y] = 'Y';  
    264. 

  264.                 break;  
    265. 

  265.             case 'd':  
    266. 

  266.                 p->cell.X += 1;  
    267. 

  267.                 maze[p->cell.X][p->cell.Y] = 'Y';  
    268. 

  268.                 break;  
    269. 

  269.             case 'l':  
    270. 

  270.                 p->cell.Y -= 1;  
    271. 

  271.                 maze[p->cell.X][p->cell.Y] = 'Y';  
    272. 

  272.                 break;  
    273. 

  273.             case 'r':  
    274. 

  274.                 p->cell.Y += 1;  
    275. 

  275.                 maze[p->cell.X][p->cell.Y] = 'Y';  
    276. 

  276.                 break;  
    277. 

  277.             }  
    278. 

  278.         }  
    279. 

  279.         else  
    280. 

  280.         {  
    281. 

  281. //          maze[p->cell.X][p->cell.Y] = 'y';  
    282. 

  282.             p = p->pro;  
    283. 

  283.             free(p->next);  
    284. 

  284.             p->next = NULL;  
    285. 

  285.         }  
    286. 

  286.     }  
    287. 

  287.     p = head;  
    288. 

  288.     while (p != NULL)  
    289. 

  289.     {  
    290. 

  290.         printf("(%d,%d)",p->cell.X,p->cell.Y);  
    291. 

  291.         p = p->next;  
    292. 

  292.     }  
    293. 

  293.     printf("\n");  
    294. 

  294. }  
    295. 

  295. int main()  
    296. 

  296. {  
    297. 

  297.     char maze[H][W];  
    298. 

  298.     PATH *head = NULL;  
    299. 

  299.     inimaze(maze);  
    300. 

  300.     creatmaze(maze);  
    301. 

  301.     print_maze(maze);  
    302. 

  302.     putout_file(maze);  
    303. 

  303.     path(maze, head);  
    304. 

  304.     print_maze2(maze);  
    305. 

  305.     Sleep(5000);  
    306. 

  306.     return 0;  
    307. 

  307.   
    308. 

  308. }  
    309. 















[cpp] view plain copy







  1. <span style="font-family:Arial, Helvetica, sans-serif;"><span style="white-space:normal;"></span></span>  








															

																					

								

									相关推荐