不学网

 找回密码
 立即注册

只需一步,快速开始

手机号码,快捷登录

查看: 334|回复: 0

[c/c++] C递归回溯,迷宫寻路

[复制链接]
j2cat 发表于 2018-1-6 18:18:25 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
  1. /*
  2. * 递归回溯,迷宫寻路DEMO
  3. */
  4. #include <stdio.h>
  5. #include <stdlib.h>

  6. int gMap[17][17] = {
  7. { 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 },
  8. { 2, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0, 2, 0, 2, 2, 0, 2 },
  9. { 2, 0, 2, 0, 2, 2, 2, 0, 0, 0, 2, 2, 0, 2, 0, 0, 2 },
  10. { 2, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 2, 0, 0, 0, 2, 2 },
  11. { 2, 0, 2, 2, 0, 2, 2, 2, 2, 0, 0, 0, 0, 2, 0, 2, 2 },
  12. { 2, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 0, 2, 0, 2, 2 },
  13. { 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 2, 2, 2, 2, 0, 2 },
  14. { 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 2, 0, 0, 2 },
  15. { 2, 0, 2, 2, 2, 2, 2, 2, 0, 2, 2, 2, 0, 2, 2, 0, 2 },
  16. { 2, 0, 2, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0, 0, 2 },
  17. { 2, 0, 2, 2, 2, 2, 0, 2, 0, 2, 2, 2, 2, 0, 2, 0, 2 },
  18. { 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 2 },
  19. { 2, 0, 2, 2, 2, 2, 2, 2, 2, 0, 2, 2, 2, 0, 2, 0, 2 },
  20. { 2, 0, 2, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 2 },
  21. { 2, 0, 0, 0, 2, 0, 0, 2, 0, 2, 0, 2, 2, 2, 2, 0, 2 },
  22. { 2, 2, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 0, 2 },
  23. { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2 }
  24. };

  25. int startX = 1,startY = 1;  // 入口
  26. int endX = 15, endY = 15;  // 出口
  27. typedef struct _tag_pos {
  28.         int ios; //x的偏移量
  29.         int jos; //y的偏移量
  30. }pos_os;

  31. pos_os pos[4] = { {-1, 0}, {1, 0},{0, -1}, {0, 1} }; //上下左右偏移量

  32. void display_map(void) {
  33.         int i, j;
  34.         for (i = 0; i < 17; i++)
  35.         {
  36.                 for (j = 0; j < 17; j++)
  37.                 {
  38.                         if (gMap[i][j] == 3) {
  39.                                 printf("|");
  40.                         }
  41.                         else if (gMap[i][j] == 2) {
  42.                                 printf("#");
  43.                         }
  44.                         else if (gMap[i][j] == 1) {
  45.                                 printf("0");
  46.                         }
  47.                         else {
  48.                                 printf(" ");
  49.                         }
  50.                                 
  51.                 }

  52.                 printf("\n");
  53.         }
  54. }

  55. int recursive_search(int x, int y) {
  56.         int ret = 0;   //接收出口返回值
  57.         gMap[x][y] = 1;
  58.         if (x == endX && y == endY) { //定义出口条件,递归边界
  59.                 ret = 1; //找到出口
  60.         }
  61.         else {
  62.                 for (int p = 0; p < 4; p++) { //上下左右4个方向
  63.                         if (gMap[x + pos[p].ios][y + pos[p].jos] == 0) {
  64.                                 ret = recursive_search(x + pos[p].ios, y + pos[p].jos); //当前位置依次上下左右4个偏移量递归寻路
  65.                                 if (ret) {
  66.                                         break; //当ret被置为真时,直接退出寻路,防止当前活动记录发生重复循环递归回溯寻路(p < 4)
  67.                                 }
  68.                         }        
  69.                 }
  70.                 if (!ret) {
  71.                         gMap[x][y] = -1;//当前所有方向偏移量寻路失败,回溯清除该步,并标记该位置防止之后发生重复循寻路
  72.                 }
  73.         }

  74.         return ret;
  75. }

  76. int main(void) {
  77.         printf("显示迷宫:\n");
  78.         display_map();
  79.         
  80.         
  81.         if (recursive_search(startX ,startY)== 0) {
  82.                 printf("\n没有找到出口!\n");
  83.         }
  84.         else {
  85.                 printf("\n显示找到出口的路径:\n");
  86.                 display_map();
  87.         
  88.         }
  89.         getchar();
  90.         return 0;
  91. }
复制代码


回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|手机版|小黑屋|不学网

GMT+8, 2018-9-19 05:01

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表