最初的想法-堆栈实现
运用深度搜索的思想，但不能保证路径是最优路径。它是找到一条能走的就一直往下挖。
1思路分析
A：行走前准备
a：规定好行走的方向，Derection Move[5]数组。 b：设置好迷宫地图，1表示墙壁，0表示小路可以行走。 c：设置好结构体类型。每个方块数据包含着两种类型数据，一种记录自己本身的坐标x，y，一种记录自己走向的下一个可走方块的方向序号。每个方向序号对应关系在Derection Move[5]数组里。
B：进行行走
a：首先将入口点信息压栈，然后进行四个方向的尝试，如果有一个为0，那么首先要对入口方块的存储的走向下一个可走方块的进行更新，入栈出栈更新。 b:将下一个可走方块信息入栈，并根据它的坐标设置迷宫图中相应位置为-1，表示已经走过。继续进行四个方向尝试，继续找0. c:如果四个方向都没有找到，说明走到死胡同，进行退栈操作，并且标记为‘X’表示此路不通。如果一直退栈，直到栈空说明该迷宫没有出路。 d:一直到某个节点的x，y坐标和终点的x,y坐标相等，则说明找到终点，程序完成。 下图，我故意构建了一种图形，可以看到他不是最优解。
1 #include2 #include 3 #include 4 #include 5 #define MAXSIZE 1024 6 typedef int elemtype; 7 typedef struct 8 { 9 int row;//横坐标方向 10 int column;//纵坐标方向 11 int direction;//从当前路径查找下一个方块的方向 12 13 }SElemType; 14 typedef struct SequenStack 15 { 16 SElemType data[MAXSIZE]; 17 int top;//top为栈顶指针 18 }SequenStack; 19 //栈的初始化 20 21 SequenStack* Init_SequenStack() 22 { 23 SequenStack *s; 24 s=(SequenStack *)malloc(sizeof(SequenStack)); 25 s->top=-1; 26 return s; 27 28 } 29 //判断栈是否为空 30 int SequenStack_Empty(SequenStack *s) 31 { 32 if(s->top==-1) 33 return 1;//栈为空，。返回1 34 else 35 return 0; 36 37 } 38 //入栈 39 int Push_SequenStack(SequenStack *s,SElemType x) 40 { 41 s->top++; 42 s->data[s->top].row=x.row; 43 s->data[s->top].direction=x.direction; 44 s->data[s->top].column=x.column; 45 return 1; 46 } 47 //出栈 48 int Pop_SequenStack(SequenStack *s,SElemType *x) 49 { 50 if(s->top==-1) 51 { 52 puts("栈为空"); 53 return 0; 54 } 55 else{ 56 57 x->column=s->data[s->top].column; 58 x->direction=s->data[s->top].direction; 59 x->row=s->data[s->top].row; 60 s->top--; 61 return 1; 62 } 63 } 64 //区栈顶元素 65 int GetTop_SequenStack(SequenStack *s,SElemType *x) 66 { 67 if(s->top==-1) 68 { 69 puts("栈为空"); 70 return 0; 71 } 72 else{ 73 x->column=s->data[s->top].column; 74 x->direction=s->data[s->top].direction; 75 x->row=s->data[s->top].row; 76 return 1; 77 } 78 79 80 81 } 82 83 84 #define SIZE 7 85 86 int Maze[SIZE][SIZE]={ 87 { 1,1,1,1,1,1,1}, 88 { 1,0,0,0,0,0,1}, 89 { 1,0,1,1,1,0,1}, 90 { 1,0,0,0,0,0,1}, 91 { 1,0,1,1,1,1,1}, 92 { 1,0,0,0,0,0,1}, 93 { 1,1,1,1,1,1,1} 94 95 /* {1,1,1,1,1,1,1}, 96 {1,0,0,0,0,0,1}, 97 {1,0,1,1,1,1,1}, 98 {1,0,0,0,0,0,1}, 99 {1,0,1,1,1,1,1},100 {1,0,0,0,0,0,1},101 {1,1,1,1,1,1,1}102 103 */104 };105 typedef struct106 {107 int x;108 int y;109 }Direction;110 Direction Move[5]={ { 0,0},{ 0,1},{ 1,0},{ 0,-1},{-1,0}};//存储东南西北方向111 112 //typedef SElemType elemtype;113 int path(SequenStack *s,int Maze[SIZE][SIZE],Direction Move[5]);114 int main()115 {116 int ii,ij,key;117 SequenStack *s;118 for(ii=0;ii
最优路径-队列实现
运用广度搜索的方法,与以上方法不同的是，它是层次搜索，它在从入口点行走时，把这个点周围的所有可以走的方块信息进行存储，保证层次相同，如果在一层中有一个到达了终点，那么它肯定是最优解，进行回溯处理，打印路径。
# include# include # include #include #include #include # define MAX 64# define M 8# define N 8int mg[M+2][N+2]={ { 1,1,1,1,1,1,1,1,1,1}, { 1,0,0,0,0,0,0,0,0,1}, { 1,0,1,1,1,1,1,1,0,1}, { 1,0,1,1,1,1,1,1,0,1}, { 1,0,0,0,0,0,0,0,0,1}, { 1,0,0,0,1,1,1,1,1,1}, { 1,0,1,0,0,0,0,0,0,1}, { 1,0,1,1,1,0,0,0,0,1}, { 1,1,0,0,0,0,0,0,0,1}, { 1,1,1,1,1,1,1,1,1,1},};typedef struct box{ int i;//当前方块的行号 int j;//当前方块的列号 int pre;//本路径上一方块在队列中的下标}Box;typedef struct{ Box data[MAX]; int front,rear;//队头指针和对尾指真}QuType;bool mgpath(int xi,int yi,int xe,int ye)//搜索路径（xi，yi）到（xe，ye）{ int i,j,find=0,di; QuType qu; qu.front=qu.rear=-1; qu.rear++; qu.data[qu.rear].i=xi; qu.data[qu.rear].j=yi;//（xi。，yi）入队 qu.data[qu.rear].pre=-1; mg[xi][yi]=-1;//将其赋值-1，避免重复搜索 while(qu.front!=qu.rear && !find) { qu.front++;//出队 i=qu.data[qu.front].i; j=qu.data[qu.front].j; if(i==xe && j==ye) { find=1; print(qu,qu.front); return true; } for(di=0;di<4;di++) { switch(di) { case 0:i=qu.data[qu.front].i-1;j=qu.data[qu.front].j;break; case 1:i=qu.data[qu.front].i;j=qu.data[qu.front].j+1;break; case 2:i=qu.data[qu.front].i+1;j=qu.data[qu.front].j;break; case 4:i=qu.data[qu.front].i;j=qu.data[qu.front].j-1;break; } if(mg[i][j]==0) { qu.rear++;//将该相邻方块插入到队列中去 qu.data[qu.rear].i=i; qu.data[qu.rear].j=j; qu.data[qu.rear].pre=qu.front;//指向上一个方块的下标 mg[i][j]=-1; } } } return false;//未找到路径时}void print(QuType qu,int front){ int k=front,i,j,ns=0; printf("\n"); do { j=k; k=qu.data[k].pre; qu.data[j].pre=-1; } while(k!=0); printf("迷宫路径如下\n"); // printf("▉"); //printf("☆"); k=0; while(k