数据结构，迷宫问题C语言版源代码

数据结构中，关于迷宫问题的源代码（C语言）。

 #include“stdio.h“
 #include“malloc.h“ 
 #include“stdlib.h“ 
 #define TRUE 1
 #define FALSE 0
 #define OK 1
 #define ERROR 0
 #define INFEASIBLE -1
 typedef int Status;


 typedef struct /* 迷宫坐标位置类型 */
 {
   int x; /* 行值 */
   int y; /* 列值 */
 }PosType;
typedef int MazeType[10][10]; /* 迷宫数组[行][列] */

 MazeType m; /* 迷宫数组 全局变量处理 因为我在初始化的时候老是弄出毛病*/
 int curstep=1; /* 当前足迹是第几个初值为1 */

 typedef struct /* 栈的元素类型 */
 {
   int ord; /* 通道块在路径上的＂序号＂ */
   PosType seat; /* 通道块在迷宫中的＂坐标位置＂ */
   int di; /* 从此通道块走向下一通道块的＂方向＂（0～3表示东～北） */
 }SElemType;

 #include“Stack.h“

/*此处因为在Stack.h中用到了SElemeType 所以在此处导入stack.h */

 /* 定义墙元素值为0可通过路径为1不能通过路径为-1通过路径为足迹记录为* */





void mazeprint（）
 { /* 输出迷宫的解 */
   int ij;
   for（i=0;i<10;i++）
  {
	  for（j=0;j<10;j++）
	  {
		  if（m[i][j]==（int） “*“）//输出时如果是* 则输出*
		    printf（“  *“）;
		  else{	  
		  printf（“ %2d“m[i][j]）;
		  if（j==9）
			  printf（“\n“）;
		  }
	  }
  }	  
 }





 Status Pass（PosType b）
 { /* 当迷宫m的b点的序号为1（可通过路径），return OK; 否则，return ERROR。 */


   if（m[b.x][b.y]==1）
     return OK;
   else
     return ERROR;
 }

 void FootPrint（PosType a）
 { /* 使迷宫m的a点的序号变为足迹（curstep） */
   m[a.x][a.y]=（int） “*“;
 }

 PosType NextPos（PosType cint di）
 { /* 根据当前位置及移动方向，返回下一位置 */
   PosType direc[4]={{01}{10}{0-1}{-10}}; /* {行增量列增量} */
   /* 移动方向依次为东南西北 */
   c.x+=direc[di].x;
   c.y+=direc[di].y;
   return c;
 }

 void MarkPrint（PosType b）
 { /* 使迷宫m的b点的序号变为-1（不能通过的路径） */
   m[b.x][b.y]=-1;
 }

 Status MazePath（PosType startPosType end） 
 { /* 若迷宫maze中存在从入口start到出口end的通道，则求得一条 */
   /* 存放在栈中（从栈底到栈顶），并返回TRUE；否则返回FALSE */
   SqStack S;
   PosType curpos;
   SElemType e;
   InitStack（&S）;
   curpos=start;
   

   do
   {
     if（Pass（curpos））/* 当前位置可以通过，即是未曾走到过的通道块 */
     { 
       FootPrint（curpos）; /* 留下足迹 */
       e.ord=curstep;
       e.seat.x=curpos.x;
       e.seat.y=curpos.y;
       e.di=0;
       Push（&Se）; /* 入栈当前位置及状态 */
       curstep++; /* 足迹加1 */
       if（curpos.x==end.x&&curpos.y==end.y） /* 到达终点（出口） */
         return TRUE;
       curpos=NextPos（curpose.di）;
     }
     else
     { /* 当前位置不能通过 */
       if（!StackEmpty（S））
       {
         Pop（&S&e）; /* 删除栈顶元素   并用e带回基本信息*/
         curstep--;
         while（e.di==3&&!StackEmpty（S）） /* 前一位置处于最后一个方向（北） 即所有方向都无法通过了*/
         {
           MarkPrint（e.seat）; /* 留下不能通过的标记（-1） */
           Pop（&S&e）; /* 退回一步 */
           curstep--;
         }
         if（e.di<3） /* 没到最后一个方向（北） */
         {
           e.di++; /* 换下一个方向探索 */
           Push（&Se）;
           curstep++;
           curpos=NextPos（e.seate.di）; /* 设定当前位置是该新方向上的相邻块 */
         }
       }
     }
   }while（!StackEmpty（S））;
   return FALSE;
 }

 void main（）
 {
   PosType beginend;
   int ij;

  MazeType newm={   
	   {0000000000}
	   {0110111010}
	   {0110011110}
	   {0111110110}
	   {000000

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       2217  2008-12-16 16:48  迷宫问题\Stack.h

     文件       4066  2008-12-16 17:16  迷宫问题\mazepath.c

     目录          0  2008-12-16 16:48  迷宫问题

----------- ---------  ---------- -----  ----

                 6283                    3