--------------------------------写在前面----------------------------------------
作为初学者的我表示这个程序真心不能自己写出来，花了一些时间才看懂@JackyBing写的这段代码，并改了一些东西
感谢@JackyBing的代码，书上的真心没看懂，现在理解了，
呜呜呜，感觉自己好弱呀，这都看了这么久，还是得像大神看齐。
一起学习，共同进步！
--------------------------------核心算法----------------------------------------
do
{
if(当前的路径可以通过）
{
留下足迹；
将当前位置保存并入栈
if（判断当前路径是否为最终路径）
{
退栈，并修改迷宫的数据，记录所走的路线
并返回 1；
}
当前步数增一；
获取下一位置；
}
else//当前位置走不通
{
if（当前栈不为空）
{
退栈；
while（当前位置的所走方向为4并且当
当前栈不为空）
{
记录当前位置不为走不通；
退栈处理；
当前步数减一；
}
if（当前的位置所走方向小于4)
{
将当前位置的方向增一；
将当前位置重新进栈；
获取下一将要通过的位置；
}
}
}
}
--摘自http://www.cnblogs.com/JackyTecblog/archive/2011/02/20/1958880.html
1 #include<iostream> 2 #include<stdlib.h> 3 4 using namespace std; 5 6 #define STACK_INIT_SIZE 100 7 #define STACKINCREASE 10 8 #define MAZESIZE 10 9 10 11 typedef struct Postion 12 { 13 int x; 14 int y; 15 }Postion; 16 17 18 typedef struct 19 { 20 Postion pos;//通道块在迷宫中的“坐标位置” 21 int curstep;//通道块在路径中的“序号” 22 int dir;//从此通道块走向下一通道块的“方向” 23 }mazenode; 24 25 26 typedef struct 27 { 28 mazenode *base; 29 mazenode *top; 30 int stacksize; 31 }SqStack,*LinkStack; 32 33 34 int InitStack(LinkStack &S) 35 { 36 S->base=(mazenode *)malloc(STACK_INIT_SIZE*sizeof(mazenode)); 37 if(!S->base) 38 { 39 cout<<"分配空间失败!"; 40 exit(-1); 41 } 42 S->top=S->base; 43 S->stacksize=STACK_INIT_SIZE; 44 return 0; 45 } 46 47 48 int Push(LinkStack &S,mazenode *e) 49 { 50 if((S->top-S->base)>=STACK_INIT_SIZE) 51 { 52 S->base=(mazenode *)realloc(S->base,(STACK_INIT_SIZE+STACKINCREASE)*sizeof(mazenode)); 53 if(!S->base) 54 { 55 cout<<"分配空间失败!"; 56 exit(-1); 57 } 58 S->top=S->base+STACK_INIT_SIZE; 59 S->stacksize=STACK_INIT_SIZE+STACKINCREASE; 60 } 61 *(S->top)=*e;//结构体 62 S->top++; 63 return 0; 64 } 65 66 67 int Pop(LinkStack &S,mazenode *e) 68 { 69 if(S->base==S->top) 70 { 71 cout<<"栈为空!"; 72 exit(0); 73 } 74 S->top--; 75 *e=*(S->top); 76 return 0; 77 } 78 79 80 int GetTop(LinkStack &S,mazenode *e) 81 { 82 if(S->base==S->top) 83 { 84 cout<<"栈为空!"; 85 return 0; 86 } 87 else 88 { 89 *e=*(S->top-1); 90 return 1; 91 } 92 } 93 94 95 int EmptyStack(LinkStack &S) 96 { 97 if(S->base==S->top) return 1;//stack is empty! 98 else return 0;//stack is not empty! 99 } 100 101 102 int Pass(Postion pos,int array[MAZESIZE][MAZESIZE])//判断pos位置是否可通 103 { 104 if(array[pos.x][pos.y]!=0&&array[pos.x][pos.y]!=-1) return 1;//indicate the way can pass 105 else return 0;//indicate the way can not pass 106 } 107 108 109 Postion NextPos(Postion pos,int dir)//结构体函数,返回当前位置下一个待判断位置的坐标，顺时针旋转(东->南->西->北) 110 { 111 switch(dir) 112 { 113 case 1:pos.y+=1;break; 114 case 2:pos.x+=1;break; 115 case 3:pos.y-=1;break; 116 case 4:pos.x-=1;break; 117 default:break; 118 } 119 return pos; 120 } 121 122 123 int MarkFoot(int arr[MAZESIZE][MAZESIZE],Postion pos)//标记已经走过了 124 { 125 arr[pos.x][pos.y]=0;//have pass by the way 126 return 0; 127 } 128 129 int MarkBlock(int arr[MAZESIZE][MAZESIZE],Postion pos) 130 { 131 arr[pos.x][pos.y]=-1;//do not pass by the postion 132 return 0; 133 } 134 135 136 int MazePath(int arr[MAZESIZE][MAZESIZE],Postion start,Postion ending) 137 { 138 LinkStack s; 139 mazenode *p=(mazenode*)malloc(sizeof(mazenode)); 140 mazenode *nodelist=(mazenode *)malloc(100*sizeof(mazenode));//记录成功路径 141 int curstep=1,flag=0;//设定入口位置为路径中的第一个位置 142 Postion curpos=start,temp;//设定当前位置为入口位置 143 InitStack(s); 144 do 145 { 146 if(Pass(curpos,arr))//当前位置可通 147 { 148 MarkFoot(arr,curpos);//很关键,标记在当前位置上的通道不能再往回走了 149 nodelist[flag].pos=curpos;//将当前位置的内容复制到nodelist数组的相应元素 150 nodelist[flag].curstep=curstep; 151 nodelist[flag].dir=1;//towards east 152 Push(s,nodelist+flag);//将nodelist数组的相应元素压入s栈中 153 flag++; 154 if(curpos.x==ending.x&&curpos.y==ending.y)//如果当前位置是终点，则依次将栈中元素的位序赋给它在数组中的相应位置 155 { 156 while(!EmptyStack(s)) 157 { 158 Pop(s,p);//p为当前路径上最后一个位置 159 arr[p->pos.x][p->pos.y]=p->curstep; 160 } 161 return 1;//结束 162 } 163 curstep++; 164 curpos=NextPos(curpos,1);//towards east 165 } 166 else//当前位置不可通 167 { 168 if(!EmptyStack(s)) 169 { 170 Pop(s,p); 171 while(p->dir==4&&!EmptyStack(s)) 172 { 173 MarkBlock(arr,p->pos);//mark that the way is not passed 174 Pop(s,p); 175 curstep--; 176 } 177 if(p->dir<4) 178 { 179 p->dir++; 180 Push(s,p); 181 temp=p->pos; 182 curpos=NextPos(temp,p->dir); 183 } 184 } 185 } 186 }while(!EmptyStack(s)); 187 return 0;//failure 188 } 189 190 191 192 int main() 193 { 194 int maze[MAZESIZE][MAZESIZE]={ 195 {0,0,0,0,0,0,0,0,0,0}, 196 {0,1,1,0,1,1,1,0,1,0}, 197 {0,1,1,0,1,1,1,0,1,0}, 198 {0,1,1,1,1,0,0,1,1,0}, 199 {0,1,0,0,0,1,1,1,1,0}, 200 {0,1,1,1,0,1,1,1,1,0}, 201 {0,1,0,1,1,1,0,1,1,0}, 202 {0,1,0,0,0,1,0,0,1,0}, 203 {0,0,1,1,1,1,1,1,1,0}, 204 {0,0,0,0,0,0,0,0,0,0}},i,j,flag; 205 Postion start,ending; 206 start.x=1;start.y=1; 207 ending.x=8;ending.y=8; 208 cout<<"primative maze:"<<endl; 209 for(i=0;i<MAZESIZE;i++) 210 { 211 for(j=0;j<MAZESIZE;j++) cout<<maze[i][j]<<" "; 212 cout<<endl<<endl; 213 } 214 flag=MazePath(maze,start,ending); 215 if(flag==1) 216 { 217 cout<<"maze processing success!"<<endl; 218 cout<<"processed maze:"<<endl; 219 for(i=0;i<MAZESIZE;i++) 220 { 221 for(j=0;j<MAZESIZE;j++) cout<<maze[i][j]<<" "; 222 cout<<endl<<endl; 223 } 224 } 225 else cout<<"maze processing fail"<<endl; 226 return 0; 227 }