C语言怎么求解迷宫问题

这篇文章主要介绍"C语言怎么求解迷宫问题"，在日常操作中，相信很多人在C语言怎么求解迷宫问题问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答"C语言怎么求解迷宫问题"的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

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语言怎么求解迷宫问题"的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注网站，小编会继续努力为大家带来更多实用的文章！