C语言数据结构中求解迷宫问题的示例分析-创新互联

这篇文章给大家分享的是有关C语言数据结构中求解迷宫问题的示例分析的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。

创新互联是一家集网站制作、网站建设、网站页面设计、网站优化SEO优化为一体的专业的建站公司,已为成都等多地近百家企业提供网站建设服务。追求良好的浏览体验,以探求精品塑造与理念升华,设计最适合用户的网站页面。 合作只是第一步,服务才是根本,我们始终坚持讲诚信,负责任的原则,为您进行细心、贴心、认真的服务,与众多客户在蓬勃发展的市场环境中,互促共生。

C语言 数据结构中求解迷宫问题实现方法

   首先求迷宫问题通常用的是“穷举求解” 即从入口出发,顺某一方向试探,若能走通,则继续往前走,否则原路返回,换另一个方向继续试探,直至走出去。

我们可以先建立一个8*8的迷宫其中最外侧为1的是墙

int mg[M+2][N+2]={
 {1,1,1,1,1,1,1,1,1,1},
 {1,0,0,1,0,0,0,1,0,1},
 {1,0,0,1,0,0,0,1,0,1},
 {1,0,0,0,0,1,1,0,0,1},
 {1,0,1,1,1,0,0,0,0,1},
 {1,0,0,0,1,0,0,0,0,1},
 {1,0,1,0,0,0,1,0,0,1},
 {1,0,1,1,1,0,1,1,0,1},
 {1,1,0,0,0,0,0,0,0,1},
 {1,1,1,1,1,1,1,1,1,1},
}

   如上所示,0对应通道方块,1代表墙。对于迷宫中的每个方块,有上下左右4个方块相邻,我们规定第i行第j列方块的位置为(i,j) 规定上方方块方位为0,顺时针方向递增编号。(i,j)上方的即为(i-1,j),下方(i+1,j),左方(i,j-1),右方(i,j+1).    为了方面回溯,我们需要有进栈出栈操作,所以我们来定义:

struct {
  int i;//当前方位行
  int j;//当前方位列
  int di;//下一个可走方位号
}St[MaxSize];//栈
int top=-1;//初始化栈顶指针

我们来看看文字过程~~

   首先将入口进栈(初始方位为-1),在栈不空的情况下循环:取栈顶方块(不退栈),若该方块是出口,则退栈。若存在这样的方块,则将其方位保存到栈顶元素中,并将这个可走的相邻方块进栈。

对应的算法:

void mgpath(int x1,int y1,int x2,int y2){
  int i.j,di,find,k;
  top++;
  St[top].i=x1; St[top].j=y1; St[top].di=-1; mg[x1][y1]=-1;

 while (top>-1){
  i=St[top].i; j=St[top].j; di=St[top].di;
  if (i==x2 && j==y2){
     printf("迷宫路径如下:\n");
    for (k=0;k<=top;k++){
      printf("\t(%d,%d)",St[k].i,S[k].j);
       if ((k+1)%5==0) printf("\n"); //输出5个换一行
       }
  printf("\n");  //找到一条路径后结束
  return ;
  }
  find=0;
  while (di<4 && find==0){
  di++;
  switch(di){
   case 0: i=St[top].i-1; j=S[top].j;break;
   case 1: i=St[top].i;  j=St[top].j+1;break;
   case 2: i=St[top].i+1;j=St[top].j;break;
   case 3: i=St[top].i;  j=St[top].j-1;break;
   }
    if(mg[i] [j]==0) find=1;
  }
  if (find==1){  //找到了下一个可走方块
   St[top].di=di;//修改原栈顶的值
   top++;  //下一个可走方块进栈
  St [top].i=i; St[top].j=j;St[top].di=-1;
  mg[i] [j]=-1;//避免重复走到该方块
 }
  else{  //没有路径可走,进行退栈操作
    mg[St[top].i] [St[top].j]=0;//让该位置变为其他路径的可走方块
    top--;
    }

}
  printf("没有路径可走!\n");
}

当然我们也可以用队列去求该迷宫的最优算法,这只是一个用来理解栈的例子~~~

感谢各位的阅读!关于“C语言数据结构中求解迷宫问题的示例分析”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!

另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。

网页题目:C语言数据结构中求解迷宫问题的示例分析-创新互联
网站路径:https://www.cdcxhl.com/article42/dpoehc.html

成都网站建设公司_创新互联,为您提供用户体验网站内链全网营销推广域名注册云服务器电子商务

广告

声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联

手机网站建设