迷宫问题实际上是一个游戏中普遍使用的搜索技术 下面我简单说一下初级的搜索技术也是最基本的搜索技术宽度优先,广度优先.

下面是迷宫程序的演示代码VC6.0通过.

#include"stdio.h"
#include"stdlib.h"
#include"iostream.h"
#define m 4
#define n 4
struct stype//设置一个迷宫节点的数据结构
{int x,y;//每个迷宫格子的坐标
}stack[400];

int mg[m+1][n+1];//设置整个寻找区间（四周外加一层障碍以便对边缘节点索）
int zx[8],zy[8];//设置八个寻找方向
void printlj(int TOP)//输出最短路径
{int i;

  for(i=1;i<=TOP;i++)
  {printf("(%d,%d)",stack[i].x,stack[i].y);
   
  }

}

void mglj()
{int i,j,x,y,top,find,v,flag;
top=1;
flag=0;
stack[1].x=1;stack[1].y=1;
find=0;
  mg[1][1]=-1;

  while(top>=1&&!find))//深度优先的搜索技术
{x=stack[top].x;
  y=stack[top].y;
   for(v=1;v<=8;v++)//扫描八个可以走的方向
   {i=x+zx[v];
    j=y+zy[v];
  if(mg[i][j]==0）//找到一个可以走的方向进入栈
  {top++;
   stack[top].x=i;
       stack[top].y=j;
  
   mg[i][j]=-1;//避免重复选择
   flag=1;     //标志在当前点可以找到一个可以走的方向
      break;           //不再对当前节点扫描
  }
     
  if(v==8)//八个方向已经被全部扫描过，无可以通的路
  {flag=0;//标志当前节点没有往前的路
  top--;  //后退一个节点搜索
  }
  

   }
   
  if((stack[top].x ==m)&&(stack[top].y ==n))//找到了目的地
  {printlj(top);//输出
  find=1;       //退出循环

  }



   

}
if(!find) printf("不存在路径\n");
}

void main()
{int i,j;
for(i=1;i<=m;i++)        //输入迷宫图形 0表示可以通 1表示不可以通
for(j=1;j<=n;j++)
scanf("%d",&mg[i][j]);

for(i=0;i<=m+1;i++)        //设置四周障碍
{mg[i][0]=1;mg[i][n+1]=1;
}
for(j=0;i<=n+1;i++)       
{mg[0][j]=1;mg[m+1][j]=1;
}

zx[1]=-1;zx[2]=-1;zx[3]=0;zx[4]=1; //设置方向
zx[5]=1;zx[6]=1;zx[7]=0;zx[8]=-1;
zy[1]=0;zy[2]=1;zy[3]=1;zy[4]=1;
zy[5]=0;zy[6]=-1;zy[7]=-1;zy[8]=-1;
mglj();
}

深度优先搜索是采用“步步为营”的方法，在特殊情况下的效率很高（如果每次很容易搜索到一个节点 并且可以通过的路比较多）但是对于那些比较复杂的路线就要搜索很久才能搜出 ，最差的就是每次必须把当前节点的所有扩展节点全部扫描过后在最后一个扫描中找到，这样也就是说每个节点都必须扫描8次（并且还要保证当前节点都有扩展节点）

那么有没有一种比较“平衡”的技术，对于一般情况效率都差不多呢？
这就有“广度优先搜索”还就上面那个程序改动一下，标志有注释的地方表示不同点
其他没标的地方和上面一下

#include"stdio.h"
#include"stdlib.h"
#define m 4
#define n 4
struct stype//有一个表示前驱的节点pre
{int x,y,pre;
}sq[400];

int mg[m+1][n+1];
int zx[8],zy[8];
void printlj(int rear)
{int i;
i=rear;
  do
  {printf("(%d,%d)",sq[i].x,sq[i].y);
   i=sq[i].pre;
  }while(i!=0);

}
void mglj()
{int i,j,x,y,front,rear,find,v;
sq[1].x=1;sq[1].y=1;sq[1].pre=0;
find=0;
front=rear=1; mg[1][1]=-1;
while(front<=rear&&!find)//广度优先的搜索技术

{x=sq[front].x;
  y=sq[front].y;
   for(v=1;v<=8;v++))//扫描全部八个方向

   {i=x+zx[v];
    j=y+zy[v];
  if(mg[i][j]==0）//把所有可以通的路放进一个队列，其中pre来表示祖先点
  {rear++;
   sq[rear].x=i;
       sq[rear].y=j;
   sq[rear].pre=front;
   mg[i][j]=-1;
   
  }
  if(i==m&&j==n)//找到了目的地
  {printlj(rear);
  find=1;
  }
   }
   front++;//前进到队列的后一个节点
}
if(!find) printf("不存在路径\n");
}

void main()
{int i,j;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
scanf("%d",&mg[i][j]);

for(i=0;i<=m+1;i++)
{mg[i][0]=1;mg[i][n+1]=1;
}
for(j=0;i<=n+1;i++)
{mg[0][j]=1;mg[m+1][j]=1;
}

zx[1]=-1;zx[2]=-1;zx[3]=0;zx[4]=1;
zx[5]=1;zx[6]=1;zx[7]=0;zx[8]=-1;
zy[1]=0;zy[2]=1;zy[3]=1;zy[4]=1;
zy[5]=0;zy[6]=-1;zy[7]=-1;zy[8]=-1;
mglj();
}

最要理解的是对八个方向任何一个满足条件的都进入队列，他和“深度优先”的区别就在于，后者是只要找到一个满足条件的路（可以通）就不再扫描，直接往“纵”扩展，而前者是对当前点扫描后，把当前点“衍生”出来的所有可以通的路都把他找出来，所以说是“横‘的扩展。
本人可能讲得不是很清晰，请仔细分析程序中的重点，相信可以找到”关键“

qq 31636451 <劲风>