设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 编程语言专区 › C\C++交流 › 迷宫问题全部路径和最短路径求解
返回列表 发新帖
查看: 4760|回复: 6

迷宫问题全部路径和最短路径求解

[复制链接]
程序员的救赎
发表于 2019-5-26 17:51:26 | 显示全部楼层 |阅读模式
60鱼币
下面的代码能找出一条路径，不知道怎么修改才能求出全部路径。

以下是输入的迷宫：
1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 0 1 1 1 1
1 1 0 1 0 1 1 1 1 1
1 0 1 0 0 0 0 0 1 1
1 0 1 1 1 0 1 1 1 1
1 1 0 0 1 1 0 0 0 1
1 0 1 1 0 0 1 1 0 1
1 1 1 1 1 1 1 1 1 1

  1. #include <iostream>
  2. #include<stack>
  3. using namespace std;
  4. /* run this program using the console pauser or add your own getch, system("pause") or input loop */
  5. const int XLEN=8,YLEN=10;//默认迷宫行数和列数
  6. int m,p;// 出口坐标
  7. int maze[XLEN][YLEN];//迷宫数组
  8. int mark[XLEN][YLEN];//访问标记数组
  9. struct Offsets{
  10.         int a,b;//a和b是x y方向的偏移
  11. };
  12. Offsets directions[8]={
  13.         {-1,0},//上
  14.         {-1,1},//右上
  15.         {0,1},//右
  16.         {1,1},//右下
  17.         {1,0},//下
  18.         {1,-1},//左下
  19.         {0,-1},//左
  20.         {-1,-1},//左上
  21. };
  22. struct items{
  23.         int x,y,dir;//栈结点定义
  24. };

  26. void outputpath(stack<items> a, items Tmp) {
  27.     stack<items> b;
  28.     b.push(Tmp);
  29.     while(!a.empty()){
  30.                                         b.push(a.top());
  31.                                         a.pop();
  32.                                 }
  33.                                 while(!b.empty()){
  34.                                         cout<<"<"<<b.top().x<<","<<b.top().y<<">"<<" ";
  35.                                         b.pop();
  36.                                     
  37.                                 }
  38. }
  39. void Path(int x,int y,int m,int n){//x,y为入口坐标，m,n为出口坐标
  40.         int i,j,g,h,d = 0; // i，j为当前位置， g,h为下一步的位置，d为下一步的方向
  41.         stack<items> S;//设置工作栈
  42.         stack<items> St;//输出栈
  43.         items tmp;
  44.         items Tmp;
  45.         mark[x][y]=1;//x,y是入口
  46.         tmp.x=x,tmp.y=y;
  47.         tmp.dir=0;
  48.         S.push(tmp);//入口坐标入栈
  49.         while(!S.empty()){//当栈不空，一直走下去
  50.                 tmp=S.top();//取栈顶元素
  51.                 S.pop();
  52.                 i=tmp.x;
  53.                 j=tmp.y;//取当前位置的坐标
  54.                 d=tmp.dir;
  55.                 while(d<8){
  56.                         //找下一位置(g,h)
  57.                         g=i+directions[d].a;
  58.                         h=j+directions[d].b;
  59.                         if(g==m && h==n){//到达出口
  60.                                 //逆向存入输出栈
  61.                                 Tmp.x=m,Tmp.y=n;
  62.                                 outputpath(S, Tmp);
  63.                                 mark[g][h]=1;//标记已被访问
  64.                                 return;
  65.                         }
  66.                
  67.                         //未到达出口
  68.                         if(maze[g][h]==0 && mark[g][h]==0){//如果可通且未被访问
  69.                                 mark[g][h]=1;//标记已被访问
  70.                                 tmp.x=i;
  71.                                 tmp.y=j;
  72.                                 tmp.dir=d;//记录已走过的位置和前进的方向
  73.                                 S.push(tmp);
  74.                                 i=g;
  75.                                 j=h;
  76.                                 d=0;}//移到(g,h)在各个方向试探
  77.                         else//试探下一个方向
  78.                                 d++;
  79.                 }
  80.         }
  81. }
  82. int main(int argc, char** argv) {
  83.         int i,j,x,y,m,n;
  84.         cout<<"迷宫如下图所示："<<endl;
  85.         for(i=0;i<XLEN;i++){
  86.                  for(j=0;j<YLEN;j++){
  87.                          cin>>maze[i][j];
  88.                          mark[i][j]=0;
  89.                  }
  90.    }
  91.                
  92.         cout<<"迷宫所有路径如下："<<endl;
  93.         Path(1,1,XLEN-2,YLEN-2);
  94. //        cout<<"最短路径如下："<<endl;
  95. //        cout<<"长度为："<<
  96. //        cout<<"通路为："<<
  97.         return 0;
  98. }
复制代码

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

程序员的救赎
 楼主| 发表于 2019-5-26 17:58:47 | 显示全部楼层
主要是最近在用Python， 大一的数据结构都忘得差不多了。
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

迷雾少年
发表于 2019-5-28 00:07:28 | 显示全部楼层
dfs可以很简单实现
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

迷雾少年
发表于 2019-5-28 00:24:38 | 显示全部楼层
  1. #include <iostream>
  2. using namespace std;
  3. //0 为可以移动 1为障碍
  4. int map[][10] =
  5. {
  6. 1,1,1,1,1,1,1,1,1,1,
  7. 1,0,1,1,1,0,1,1,1,1,
  8. 1,0,0,0,0,1,1,1,1,1,
  9. 1,0,1,0,0,0,0,0,1,1,
  10. 1,1,1,1,1,0,1,1,1,1,
  11. 1,0,0,0,0,0,0,0,0,1,
  12. 1,0,1,1,0,0,1,1,0,1,
  13. 1,0,0,0,0,0,0,0,0,1 };
  14. struct point
  15. {
  16.         int x, y;
  17. };
  18. point steps[100] = { 0 };
  19. int startx = 1, starty = 1;
  20. int endx = 5, endy = 3;
  21. int direct[][2] = { {-1,0},{1,0},{0,-1},{0,1} };
  22. int row = 8, col = 10;//8行10列地图

  24. void dfs(int deep, int x, int y)
  25. {
  26.         int i;
  27.         if (x<0 || x>row - 1 || y<0 || y>col - 1 || map[x][y] == 1)
  28.                 return;
  29.         point tmp = { x,y };
  30.         steps[deep] = tmp;
  31.         if (x == endx && y == endy) {//终点
  32.                 for (i = 0; i < deep+1; i++) {
  33.                         printf("(%d,%d)-", steps[i].x, steps[i].y);
  34.                 }
  35.                 printf("\n");
  36.                 return;
  37.         }
  38.         for (i = 0; i < 4; i++)
  39.         {
  40.                 map[x][y] = 1;
  41.                 dfs(deep + 1, x + direct[i][0],y+direct[i][1]);
  42.                 map[x][y] = 0;
  43.         }
  44. }

  46. int main()
  47. {
  48.         point t = { startx,starty };
  49.         dfs(0, startx, starty);
  50.         return 0;
  51. }
复制代码



(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(6,5)-(7,5)-(7,4)-(6,4)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(6,5)-(7,5)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(6,5)-(6,4)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(6,5)-(6,4)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(5,4)-(6,4)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(5,4)-(6,4)-(6,5)-(7,5)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)-(5,7)-(5,8)-(6,8)-(7,8)-(7,7)-(7,6)-(7,5)-(6,5)-(6,4)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)-(5,7)-(5,8)-(6,8)-(7,8)-(7,7)-(7,6)-(7,5)-(6,5)-(6,4)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)-(5,7)-(5,8)-(6,8)-(7,8)-(7,7)-(7,6)-(7,5)-(7,4)-(6,4)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)-(5,7)-(5,8)-(6,8)-(7,8)-(7,7)-(7,6)-(7,5)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(6,5)-(7,5)-(7,4)-(6,4)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(6,5)-(7,5)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(6,5)-(6,4)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(6,5)-(6,4)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(5,4)-(6,4)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(5,4)-(6,4)-(6,5)-(7,5)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)-(5,7)-(5,8)-(6,8)-(7,8)-(7,7)-(7,6)-(7,5)-(6,5)-(6,4)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)-(5,7)-(5,8)-(6,8)-(7,8)-(7,7)-(7,6)-(7,5)-(6,5)-(6,4)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)-(5,7)-(5,8)-(6,8)-(7,8)-(7,7)-(7,6)-(7,5)-(7,4)-(6,4)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)-(5,7)-(5,8)-(6,8)-(7,8)-(7,7)-(7,6)-(7,5)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

程序员的救赎
 楼主| 发表于 2019-5-28 09:41:38 | 显示全部楼层
迷雾少年 发表于 2019-5-28 00:24
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(6,5)-(7,5)-(7,4)-(6,4)-(5,4)-(5,3)-
(1 ...

···你这个是四个方向的，我的是八个方向的，而且我想要的是在我基础上上面修改一下
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

迷雾少年
发表于 2019-5-28 16:10:58 | 显示全部楼层
程序员的救赎 发表于 2019-5-28 09:41
···你这个是四个方向的，我的是八个方向的，而且我想要的是在我基础上上面修改一下

八个方向x-1,y-1,x+1,y+1,x-1,y+1,x-1,y+1就可以了
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

迷雾少年
发表于 2019-5-28 16:12:06 | 显示全部楼层
程序员的救赎 发表于 2019-5-28 09:41
···你这个是四个方向的，我的是八个方向的，而且我想要的是在我基础上上面修改一下

dfs递归用的就是栈啊，原理一样
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-2 05:06

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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