QQ登录

只需一步,快速开始

搜索
查看: 137|回复: 10

迷宫问题怎么解决?具体思路和算法

[复制链接]
最佳答案
0 
累计签到:11 天
连续签到:11 天
发表于 2017-10-13 00:22:29 | 显示全部楼层 |阅读模式

马上注册加入鱼C,享用更多服务吧^_^

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

x
要求:
        1.地图给定,出发点给定,终点给定
        2,打印出所有可以到达终点的路径

给定的地图

给定的地图
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
1 
累计签到:21 天
连续签到:6 天
发表于 2017-10-13 15:39:39 | 显示全部楼层
分析:
①地形原因,起点在左上,终点在右下,能走到的方法肯定是向右走或者向下走;
②地形上每个点作为一个位置,可以移动的方向有上下左右4个方向。一个点向右方或者下方作判断,不是墙就可以移动(移动方向不与上一次操作方向相反就行,比如上一步是向下走,这一步不能向上走了);
③在起始点,移动判断(记录每一步的移动方向),会出现多个可以移动的点,每个可以移动的点作一个分支(先认为都是可行的方法,记录该分支的移动方向)处理。当其中一个分支走到死路时(没有可以移动的方向),该分支不是一个可行的方法。最后剩下来的就是各种不同的路线了。
--------------------------------------------------------------------------------
以上只是针对该图的简单分析,依据此方法编写代码应该不是问题了。
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
4 
累计签到:10 天
连续签到:1 天
发表于 2017-10-13 16:42:33 | 显示全部楼层
本帖最后由 橙C 于 2017-10-13 16:43 编辑

百度"C 寻路" 或者 "C 迷宫"~
答案多了去了....
转载一段别人的代码~
按4回车...出离开迷宫所有路径~
  1. /***********************************
  2. *
  3. * 图的矩阵表示及其深度遍历和广度遍历
  4. *
  5. * 深搜和广搜其实可以分别归结到回溯和分支界限法,
  6. * 回溯和分支界限都有两种树,一种叫子集树,一种叫
  7. * 排序树。在处理该类问题时,要注意剪枝:其中包括
  8. * 约束函数和界限函数两种!
  9. *
  10. * 为了模拟深度遍历和广度遍历,我假设了一个问题是
  11. * 走迷宫,遇到0表示可通过,其中:
  12. * 1.深度优先将把所有能成功走出的路径输出
  13. * 2.广搜则输出所有路径最短的路径,而广搜的时候需要
  14. * 用到队列,目前不想用STL,所以直接自己写队列了
  15. *
  16. * author: huangkq1989
  17. * blog:   http://blog.csdn.net/kangquan2008
  18. * 转载请标明源博客,谢谢 :)
  19. *
  20. ***********************************/
  21. #include <stdio.h>
  22. #include <stdlib.h>
  23. #include <string.h> /*for memset and memcpy*/

  24. #define X_SIZE 5
  25. #define Y_SIZE 5

  26. /////////////////////////////////////////深度////////////////////////////////////////////////////
  27. int dir[][2] = {{1,0},{-1,0},{0,1},{0,-1}};
  28. int matrix[X_SIZE][Y_SIZE] = {0,2,3,4,5,
  29.         0,1,0,0,0,
  30.         0,0,1,1,1,
  31.         1,0,0,0,0,
  32.         0,1,1,0,0};
  33. int used[X_SIZE][Y_SIZE] = {0};

  34. // 属于排序树
  35. void dfs(int x,int y)
  36. {
  37.         if(x == X_SIZE || y == Y_SIZE)
  38.         {
  39.                 for(int i=0; i<X_SIZE; i++)
  40.                         for(int j=0; j<Y_SIZE; j++)
  41.                                 printf("%d %s",matrix[i][j],(j==Y_SIZE-1)?"\n":"");
  42.                 printf("--------------\n");
  43.                 return ;       
  44.         }

  45.         for(int k=0; k<4; k++)
  46.         {
  47.                 if(matrix[x][y] == 0 && used[x][y] == 0
  48.                                 && x >=0 && x < X_SIZE
  49.                                 && y >=0 && y < Y_SIZE )
  50.                 {
  51.                         // 这一条件是为了避免当 matrix[X_SIZE-1][Y_SIZE-1] = 0 时输出两次!是否还有其他解决方法呢?知道的同学请回复
  52.                         if(x+dir[k][0] == X_SIZE-1 && y+dir[k][1] == Y_SIZE)
  53.                                 ;
  54.                         else
  55.                         {
  56.                                 used[x][y] = 1;
  57.                                 matrix[x][y] = 8;
  58.                                 dfs(x+dir[k][0],y+dir[k][1]);
  59.                                 matrix[x][y] = 0;
  60.                                 used[x][y] = 0;
  61.                         }
  62.                 }
  63.         }
  64. }

  65. /////////////////////////////////////////深度////////////////////////////////////////////////////


  66. /////////////////////////////////////////广度////////////////////////////////////////////////////

  67. #define QUEUE_LENGTH 10000
  68. #define CHECK_RET(ret,info) \
  69.         if((ret) < 0) {printf("%s\n",info);continue;}

  70. typedef struct Point
  71. {
  72.         int x;
  73.         int y;
  74.         struct Point* pre;  // 保存路径中的上一个节点
  75. }Point;
  76. typedef struct Queue
  77. {
  78.         int head;
  79.         int tail;
  80.         Point path[QUEUE_LENGTH];
  81. }Queue;

  82. // 队列的函数被放到后面
  83. void queue_initial(Queue *que);
  84. int queue_empty(Queue * que);
  85. int queue_full(Queue * que);
  86. int queue_push(Queue * que,Point point);
  87. int queue_top(Queue * que,Point *point);
  88. int queue_pop(Queue * que,Point *point);
  89. void queue_test(Queue * que);

  90. // 递归地输出路径
  91. void print_path(Point *point)
  92. {
  93.         if(point->pre == NULL)
  94.                 return;
  95.         else
  96.         {
  97.                 print_path(point->pre);
  98.                 printf("x:%d y:%d\n",point->x,point->y);
  99.         }

  100. }

  101. void bfs(int x,int y,Queue * que)
  102. {
  103.         if(x >=0 && x < X_SIZE && y >=0 && y < Y_SIZE && used[x][y] == 0 && matrix[x][y] == 0)
  104.         {
  105.                
  106.                 Point point;
  107.                 point.x = x;
  108.                 point.y = y;
  109.                 point.pre = NULL;
  110.                 used[x][y] = 1;
  111.                 queue_push(que,point);
  112.         }

  113.         int path_index = 0;
  114.         while(!queue_empty(que))
  115.         {
  116.                 Point point2;
  117.                 queue_pop(que,&point2);
  118.                 if(point2.x == X_SIZE-1 || point2.y == Y_SIZE-1)
  119.                 {
  120.                         //printf("x:%d, y:%d\n",point2.x,point2.y);
  121.                         print_path(&point2);
  122.                         printf("====================\n");
  123.                         continue;
  124.                 }
  125.                 for(int k=0; k<4; k++)
  126.                 {
  127.                         int new_x = point2.x+dir[k][0];
  128.                         int new_y = point2.y+dir[k][1];
  129.                         if( new_x >=0 && new_x < X_SIZE
  130.                                 && new_y >=0 && new_y < Y_SIZE
  131.                                 && matrix[new_x][new_y] == 0 && used[new_x][new_y] == 0 )
  132.                         {

  133.                                 Point point3;
  134.                                 point3.x = new_x;
  135.                                 point3.y = new_y;

  136.                                 Point * save_point = (Point* )malloc(sizeof(Point));
  137.                                 memcpy(save_point,&point2,sizeof(Point));
  138.                                 point3.pre = save_point;

  139.                                 used[new_x][new_y] = 1; // 只有一次机会成为扩展机会
  140.                                 queue_push(que,point3);
  141.                         }
  142.                 }
  143.         }
  144. }

  145. /////////////////////////////////////////广度////////////////////////////////////////////////////

  146. int main()
  147. {
  148.         Queue queue;
  149.         queue_initial(&queue);
  150.         queue_test(&queue);
  151.         dfs(0,0);
  152.         bfs(0,0,&queue);
  153.         return 0;
  154. }

  155. /////////////////////////////////////////队列////////////////////////////////////////////////////
  156. void queue_initial(Queue *que)
  157. {
  158.         que->head = que->tail = 0;
  159.         memset(que->path,0,sizeof(que->path));
  160.         que->path->pre = NULL;
  161. }

  162. int queue_empty(Queue * que)
  163. {
  164.         return que->head == que->tail;
  165. }

  166. int queue_full(Queue * que)
  167. {
  168.         return (que->tail+1)%QUEUE_LENGTH == que->head;
  169. }

  170. int queue_push(Queue * que,Point point)
  171. {
  172.         if(queue_full(que))
  173.                 return -1;
  174.         que->path[(que->tail++)%QUEUE_LENGTH] = point;
  175.                 return 0;
  176. }

  177. int queue_top(Queue * que,Point *point)
  178. {
  179.         if(queue_empty(que))
  180.                 return -1;
  181.         *point = que->path[que->head];
  182.         return 0;
  183. }

  184. int queue_pop(Queue * que,Point *point)
  185. {
  186.         if(queue_empty(que))
  187.                 return -1;
  188.         *point = que->path[(que->head++)%QUEUE_LENGTH];
  189.         return 0;
  190. }

  191. void queue_test(Queue * que)
  192. {
  193.         int i,j;
  194.         i=j=0;
  195.         while(1)
  196.         {
  197.                 int choice;
  198.                 Point point;
  199.                 printf("%s","1 for push,2 for pop,3 for top,4 for exit\n");
  200.                 scanf("%d",&choice);
  201.                 switch(choice)
  202.                 {
  203.                         case 1:
  204.                                 point.x = i++;
  205.                                 point.y = j++;
  206.                                 point.pre = NULL;
  207.                                 CHECK_RET(queue_push(que,point),"full");
  208.                                 break;
  209.                         case 2:
  210.                                 CHECK_RET(queue_pop(que,&point),"empty");
  211.                                 printf("x:%d y:%d\n",point.x,point.y);
  212.                                 break;
  213.                         case 3:
  214.                                 CHECK_RET(queue_top(que,&point),"empty");
  215.                                 printf("x:%d y:%d\n",point.x,point.y);
  216.                                 break;
  217.                         case 4:
  218.                                 goto L;
  219.                                 break;
  220.                         default:
  221.                                 break;
  222.                 }
  223.         }
  224. L:
  225.         ;
  226. }

  227. /////////////////////////////////////////队列////////////////////////////////////////////////////
复制代码
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
0 
累计签到:11 天
连续签到:11 天
 楼主| 发表于 2017-10-13 21:16:47 | 显示全部楼层
橙C 发表于 2017-10-13 16:42
百度"C 寻路" 或者 "C 迷宫"~
答案多了去了....
转载一段别人的代码~

亲 能否整理一下符合能输出所有路径的程序,加上详细备注,便于小白们理解哦
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
0 
累计签到:11 天
连续签到:11 天
 楼主| 发表于 2017-10-13 21:17:26 | 显示全部楼层
U201010009 发表于 2017-10-13 15:39
分析:
①地形原因,起点在左上,终点在右下,能走到的方法肯定是向右走或者向下走;
②地形上每个点作为 ...

不行的啊。不能投机取巧
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
4 
累计签到:10 天
连续签到:1 天
发表于 2017-10-14 09:30:05 | 显示全部楼层
谢坡坡 发表于 2017-10-13 21:16
亲 能否整理一下符合能输出所有路径的程序,加上详细备注,便于小白们理解哦

不怕告诉你..
我也不理解...
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
0 
累计签到:11 天
连续签到:11 天
 楼主| 发表于 2017-10-14 21:18:08 | 显示全部楼层
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
0 
累计签到:11 天
连续签到:11 天
 楼主| 发表于 2017-10-14 21:19:25 | 显示全部楼层
橙C 发表于 2017-10-14 09:30
不怕告诉你..
我也不理解...

不会做。打错了。这个题应该是图的深度优先遍历。还要设置栈。结构体。。。。。等等。很多的技术细节啊。
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
4 
累计签到:10 天
连续签到:1 天
发表于 7 天前 | 显示全部楼层
谢坡坡 发表于 2017-10-14 21:19
不会做。打错了。这个题应该是图的深度优先遍历。还要设置栈。结构体。。。。。等等。很多的技术细节啊。 ...

新手就跳过吧..
老手都不一定会理解...
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
1 
累计签到:21 天
连续签到:6 天
发表于 6 天前 | 显示全部楼层
谢坡坡 发表于 2017-10-13 21:17
不行的啊。不能投机取巧

我这分析的是特殊情况,你自己思考下,很容易想出完整的解决方案的。移动无非就是上下左右4个方向,问题是怎么走,怎么判断!这个你该好好思考下
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
0 
累计签到:11 天
连续签到:11 天
 楼主| 发表于 6 天前 | 显示全部楼层
U201010009 发表于 2017-10-16 17:45
我这分析的是特殊情况,你自己思考下,很容易想出完整的解决方案的。移动无非就是上下左右4个方向,问题 ...

1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐上一条 /1 下一条

小黑屋手机版Archiver( 粤公网安备 44051102000370号 | 粤ICP备11014136号

© 2010-2017 FishC.com GMT+8, 2017-10-22 03:35 Powered by Discuz! X2.5 Theme by dreambred

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