QQ登录

只需一步,快速开始

登录 | 立即注册 | 找回密码

主题

帖子

荣誉

VIP至尊会员

Rank: 15Rank: 15Rank: 15

积分
29
查看: 165|回复: 1

[技术交流] 输出迷宫的最短路径

[复制链接]
最佳答案
0 
累计签到:27 天
连续签到:1 天
谢坡坡 发表于 2017-10-16 09:46:34 1651 | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 谢坡坡 于 2017-10-16 09:48 编辑
  1. #include<stdio.h>  
  2. #define M 8   //行数  
  3. #define N 8     //列数  
  4. #define MaxSize    100     //栈最多元素个数  
  5. int mg[M+2][N+2]={      //一个迷宫,其四周要加上均为1的外框  
  6.                     {1,1,1,1,1,1,1,1,1,1},  
  7.                     {1,0,0,0,0,0,0,0,0,1},  
  8.                     {1,0,0,1,1,0,1,1,0,1},  
  9.                     {1,0,0,1,0,0,1,0,0,1},  
  10.                     {1,0,1,1,1,0,1,1,0,1},  
  11.                     {1,0,0,1,0,0,1,0,0,1},  
  12.                     {1,0,0,1,1,0,1,0,0,1},  
  13.                     {1,0,1,0,0,0,0,1,0,1},  
  14.                     {1,0,0,0,0,1,0,0,0,1},  
  15.                     {1,1,1,1,1,1,1,1,1,1}  
  16. };  
  17. struct migong{  
  18.     int i;      //路径横坐标  
  19.     int j;      //路径纵坐标  
  20.     int di;     //方向  
  21. }Stack[MaxSize],Path[MaxSize];      //定义栈和存放最短路径的数组  
  22. int top=-1;     //栈顶指针  
  23. int count=1;    //路径数计数  
  24. int minlen=MaxSize;     //最短路径长度  
  25. void mgpath()
  26. {      //路径为:(1,1)->(M,N)  
  27.     int i,j,di,find,k;  
  28.     top++;
  29.         Stack[top].i=1;
  30.         Stack[top].j=1;
  31.         Stack[top].di=-1;  //第一个点入栈
  32.     mg[1][1]=-1;        //初始结点进栈  

  33.     while(top>-1)
  34.         {      //栈不空时循环  
  35.         i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;  
  36.         if(i==M && j==N)
  37.                 {       //找到了出口,输出路径  
  38.             printf("M:  ",count++);  
  39.             for(k=0;k<=top;k++)
  40.                         {  
  41.                 printf("(%d,%d)  ",Stack[k].i,Stack[k].j);  
  42.                 if((k+1)%5==0)      //输出时每5个结点换一行  
  43.                     printf("\n\t");  
  44.             }  
  45.             printf("\n");  
  46.             if(top+1<minlen)
  47.                         {       //比较输出最短路径  
  48.                 for(k=0;k<=top;k++)  
  49.                     Path[k]=Stack[k];  
  50.                 minlen=top+1;  
  51.             }  
  52.             mg[Stack[top].i][Stack[top].j]=0;   //让该位置变为其他路径的可走结点  
  53.             top--;  
  54.             i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;  
  55.         }  
  56.         find=0;  
  57.         while(di<4 && find==0)
  58.                 {     //找下一个可走结点  
  59.             di++;  
  60.             switch(di)
  61.                         {  
  62.                 case 0:i=Stack[top].i-1;j=Stack[top].j;break;   //上面  
  63.                 case 1:i=Stack[top].i;j=Stack[top].j+1;break;   //右边  
  64.                 case 2:i=Stack[top].i+1;j=Stack[top].j;break;   //下面  
  65.                 case 3:i=Stack[top].i;j=Stack[top].j-1;break;   //左边  
  66.             }  
  67.             if(mg[i][j]==0)  
  68.                 find=1;  
  69.         }  
  70.         if(find == 1)
  71.                 {      //找到了下一个可走结点  
  72.             Stack[top].di=di;   //修改原栈顶元素的di值  
  73.             top++;      //下一个可走结点进栈  
  74.             Stack[top].i=i;  
  75.             Stack[top].j=j;  
  76.             Stack[top].di=-1;  
  77.             mg[i][j]=-1;        //避免重复走到该结点  
  78.         }
  79.                 else
  80.                 {  
  81.             mg[Stack[top].i][Stack[top].j]=0;   //让该位置变为其他路径的可走结点  
  82.             top--;  
  83.         }  
  84.     }  
  85.     printf("最短路径如下:\n");  
  86.     printf("长度:  %d\n",minlen);  
  87.     printf("路径:  ");  
  88.     for(k=0;k<minlen;k++)
  89.         {  
  90.         printf("(%d,%d)  ",Path[k].i,Path[k].j);  
  91.         if((k+1)%5==0)      //输出时每5个结点换一行  
  92.             printf("\n\t");  
  93.     }  
  94.     printf("\n");  
  95. }  
  96. int main(){  
  97.     printf("迷宫所有路径如下:\n");  
  98.     mgpath();  
  99.     return 0;  
  100. }
复制代码
楼层
跳转到指定楼层
最佳答案
0 

尚未签到

loewe 发表于 2017-11-11 11:09:38 | 显示全部楼层
楼主厉害了,学习一下

发表回复

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

本版积分规则

关闭

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

    移动客户端下载(未启用)
    微信公众号

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备11014136号

Copyright 2018 鱼C论坛 版权所有 All Rights Reserved.

Powered by Discuz! X3.1 Copyright
© 2001-2018 Comsenz Inc.    All Rights Reserved.

小黑屋|手机版|Archiver|鱼C工作室 ( 粤公网安备 44051102000370号 | 粤ICP备11014136号

GMT+8, 2017-11-25 06:19

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