曾经用C语言做过的动态走迷宫程序,先分享代码如下:
代码如下:
1 //头文件 2 #include3 #include //Sleep(500)函数调用此头文件 4 #include //getch()函数调用此头文件 5 #include //system("cls")函数调用此头文件 6 7 //函数状态码定义 8 /******************************/ 9 #define TRUE 1 10 #define FALSE 0 11 #define OK 1 12 #define ERROR 0 13 #define INFEASIBLE -1 14 #define OVERFLOW -2 15 typedef int Status; 16 #define STACK_INIT_SIZE 100 17 #define STACKINCREMENT 10 18 #define Pass 0 //可通过 19 #define Wall 1 //墙 20 #define Start 6 //起点 21 #define End 7 //终点 22 #define Back 8 //返回 23 #define Exit 9 //出口:找到终点后标志出来 24 /******************************/ 25 26 //自定义数据类型 27 /***************************************************/ 28 29 //自定义枚举类型 30 enum direction{East=2,South,West,North};//2,3,4,5分别代表东、南、西、北 31 /*+------------------------ 32 使用枚举类型来表示方向 33 该枚举类型定义的变量只能取值 East,West,South,North 34 且East=2,South=3,West=4,North=5 35 本源码上面使用枚举类型,基本等效于下面 36 #define East 2 37 #define South 3 38 #define West 4 39 #define North 5 40 +------------------------*/ 41 42 //自定义坐标结构体 43 typedef struct //迷宫x行,y列 44 { 45 int x; 46 int y; 47 }Position;//坐标结构体 48 49 //二维数组构造迷宫,1代表墙,0代表可通过。 50 int Map[10][10]={ 51 { 1,6,1,1,1,1,1,1,1,1}, 52 { 1,0,0,1,0,0,0,1,0,1}, 53 { 1,0,0,1,0,0,0,1,0,1}, 54 { 1,0,0,0,0,1,1,0,0,1}, 55 { 1,0,1,1,1,0,0,0,0,1}, 56 { 1,0,0,0,1,0,0,0,0,1}, 57 { 1,0,1,0,0,0,1,0,0,1}, 58 { 1,0,1,1,1,0,1,1,0,1}, 59 { 1,1,0,0,0,0,0,0,0,7}, 60 { 1,1,1,1,1,1,1,1,1,1} 61 }; 62 63 //自定义结构体作为中间变量保存当前临时坐标信息 64 typedef struct 65 { 66 int number;//记录是第几步 67 Position seat;//通道块在迷宫中的"位置坐标" 68 enum direction direc; 69 //direction为枚举类型,用来表示从此通道走向下一通道的方向 70 //direc只能取值 East,West,South,North 71 //且East=2,South=3,West=4,North=5 72 }SElemType; 73 74 //自定义栈结构便于将上面结构体的临时坐标信息放到栈内存储 75 typedef struct { 76 SElemType *base; 77 SElemType *top; 78 int stacksize; 79 }SqStack;//栈 80 /*********************************************/ 81 82 //函数声明 83 /******************************************/ 84 85 void Welcome();//欢迎界面函数 86 void printfMap();//打印迷宫函数 87 Status findPath(SqStack &S,Position start,Position end);//迷宫寻路径函数 88 Status InitStack(SqStack &S);//初始化栈 89 Status StackEmpty(SqStack S);//判断栈是否为空 90 Status Push(SqStack &S,SElemType e);//入栈 91 Status Pop(SqStack &S,SElemType &e);//出栈 92 enum direction Judge_direc(Position pos);//根据一个坐标探索周围坐标返回可通行的坐标 93 Position change_seat(Position &pos,enum direction direc);//根据方向移动到下一个可通行的坐标处 94 Status change_Map(int mapid); 95 96 /****************主函数开始***********************/ 97 98 //主函数 99 int main()100 {101 Position start,end;102 int n;103 SqStack S;104 InitStack(S);//初始化栈105 Welcome();//调用欢迎界面函数106 start.x=0;//0107 start.y=1;//1108 printf("请选择地图:\n\n");109 change_Map(0);110 printf("\t\t默认地图0\n\n");111 printfMap();112 change_Map(1);113 printf("\t\t备选地图1\n\n");114 printfMap();115 printf("选择默认地图请输入0,备选地图请输入1:\n");116 printf("您的选择:");117 scanf("%d",&n);118 system("cls");119 switch(n)120 {121 case 0:122 {123 change_Map(0);printf("初始迷宫如下所示:\n\n");124 end.x=8;end.y=9;125 printfMap();126 printf("按任意键继续!");127 getch();128 system("cls");129 break;130 }131 case 1:132 {133 change_Map(1);printf("初始迷宫如下所示:\n\n"); 134 end.x=0;135 end.y=8;136 printfMap();137 printf("按任意键继续!");138 getch();139 system("cls");140 break;141 }142 }143 findPath(S,start,end);144 printf("\n\n按下任意键退出系统!\n");145 getch();146 147 return 0;148 }149 /***************主函数结束***********************/150 //打印迷宫151 void printfMap()152 {153 int i,j;154 for(i=0;i<10;i++)155 {156 printf("\t");157 for(j=0;j<10;j++)158 switch(Map[i][j]){159 case Pass:printf("□");break;//可通过0160 case Wall:printf("■");break;//墙1161 case East:printf("→");break;//东2162 case South:printf("↓"); break;//南3163 case West:printf("←");break;//西4164 case North:printf("↑");break;//北5165 case Start:printf("⊙");break;//起点6166 case End:printf("◎");break;//终点7167 case Back:printf("Θ");break;//返回8168 case Exit:printf("To");break;//出口9169 }170 printf("\n");171 }172 printf("\n");173 }174 175 //走迷宫176 Status findPath(SqStack &S,Position start,Position end){177 Position curpos;//当前坐标178 SElemType elem;//路径相关信息结构体179 int step=1;//记录步骤数180 curpos=start;//开始坐标 181 while(1){182 if(curpos.x==start.x&&curpos.y==start.y)//此段代码只执行一次183 {184 elem.number=1;185 elem.direc=Judge_direc(curpos);//判断下一个位置是什么方向186 elem.seat=curpos;187 step++;188 Push(S,elem);//第一个起点无条件入栈 189 } 190 191 Map[curpos.x][curpos.y]=(int)elem.direc;//锁定当前位置192 curpos=change_seat(curpos,elem.direc);//移动到下一个位置,根据方向改变坐标位置193 if(Map[curpos.x][curpos.y]==End)//找到终点,退出循环194 {195 elem.seat=curpos;196 elem.number=step;197 Push(S,elem);198 Map[curpos.x][curpos.y]=Exit;199 system("cls");200 printf("\n");201 printfMap();202 printf("\n\t恭喜您,迷宫路径已经找到!\n\n");203 printf("路径坐标为:\n\n");204 while(!StackEmpty(S))205 {206 Pop(S,elem);//出栈207 curpos=elem.seat;208 printf("(%d,%d)\t",curpos.x,curpos.y);209 }210 break;211 }212 if(Map[curpos.x][curpos.y]==Pass)//如果当前路可通213 {214 elem.number=step;215 elem.seat=curpos;216 elem.direc=Judge_direc(curpos);217 Push(S,elem);//将当前坐标入栈218 step++;219 }220 else//如果当前位置不通221 {222 Pop(S,elem);223 curpos=elem.seat;224 step=elem.number-1;225 Map[curpos.x][curpos.y]=Back;//表示四个都不通,标记走过了226 do227 {228 Pop(S,elem);//出栈229 curpos=elem.seat; 230 /************while循环开始*****************/231 while(elem.direc<=4)232 {233 elem.direc=(enum direction)(elem.direc+1);234 curpos=change_seat(curpos,elem.direc);//移动到下一个位置,根据方向改变坐标位置235 if(Map[curpos.x][curpos.y]==Pass)236 {237 break;238 }239 };240 /************while循环结束*****************/241 if(Map[curpos.x][curpos.y]==Pass)242 {243 curpos=elem.seat;244 elem.number=step;245 elem.seat=curpos;246 Push(S,elem);247 step++;248 break;249 }250 else251 {252 curpos=elem.seat;253 Map[curpos.x][curpos.y]=Back; 254 }255 printf("正在遍历查找...\n\n");256 printfMap();257 Sleep(1000);258 system("cls");259 }while(!StackEmpty(S));//直到栈为空跳出循环 260 }261 printf("正在遍历查找...\n\n");262 printfMap();263 Sleep(1000);264 system("cls");265 }266 return OK; 267 }268 269 //改变坐标270 Position change_seat(Position &pos,enum direction direc){271 switch(direc)272 {273 case East: pos.y=pos.y+1;break;//2274 case South: pos.x=pos.x+1;break;//3275 case West: pos.y=pos.y-1;break;//4276 case North: pos.x=pos.x-1;break;//5277 }278 return pos;279 }280 //判断下一个位置方向281 enum direction Judge_direc(Position pos)282 {283 enum direction judge;284 if(Map[pos.x][pos.y+1]==Pass||Map[pos.x][pos.y+1]==End)285 judge=East;286 else287 {288 if(Map[pos.x+1][pos.y]==Pass||Map[pos.x+1][pos.y]==End)289 judge=South;290 else291 {292 if(Map[pos.x][pos.y-1]==Pass||Map[pos.x][pos.y-1]==End)293 judge=West;294 else295 {296 if(Map[pos.x-1][pos.y]==Pass||Map[pos.x-1][pos.y]==End)297 judge=North;298 }299 }300 }301 return judge; 302 }303 304 Status change_Map(int mapid)305 {306 if(mapid==0)//默认地图307 {308 Map[0][8]=Wall;309 Map[8][9]=End;310 }311 if(mapid==1)//其他地图312 {313 Map[8][9]=Wall;314 Map[0][8]=End;315 }316 return OK;317 }318 319 //初始化栈320 Status InitStack(SqStack &S){321 S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));322 if(!S.base)exit(OVERFLOW);323 S.top=S.base;324 S.stacksize=STACK_INIT_SIZE;325 return OK;326 }327 328 //判断栈是否为空329 Status StackEmpty(SqStack S){330 if(S.top==S.base)331 return TRUE;332 else333 return FALSE;334 }335 //入栈336 Status Push(SqStack &S,SElemType e){337 if(S.top-S.base>=S.stacksize){338 S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));339 if(!S.base)exit(OVERFLOW);340 S.top=S.base+S.stacksize;341 S.base+=STACKINCREMENT;342 }343 *S.top++=e;344 return OK;345 }346 347 //出栈348 Status Pop(SqStack &S,SElemType &e){349 if(S.top==S.base)return ERROR;350 e=*--S.top;351 return OK;352 }353 //去栈顶元素354 Status GetTop(SqStack S,SElemType &e){355 356 if(S.top==S.base)return ERROR;357 358 e=*(S.top-1); //注意top指向待插入位置359 360 return OK;361 362 }363 364 //欢迎界面函数365 void Welcome(){366 system("title 迷宫求解程序");//设置窗口标题367 system("mode con cols=80 lines=40"); //窗口宽度高度368 system("color a");//设置文本颜色,所在头文件369 printf("★**************************************************************★\n");370 printf("★ ★\n");371 printf("★ 欢迎使用迷宫求解程序 ★\n");372 printf("★ ★\n");373 printf("★ 文件名称:数据结构期末实验 ★\n");374 printf("★ ★\n");375 printf("★ 项目名称:迷宫求解程序 ★\n");376 printf("★ ★\n");377 printf("★ 创建时间:2014-11-28 ★\n");378 printf("★ ★\n");379 printf("★ 最后修改时间:2014-12-2 ★\n");380 printf("★ ★\n");381 printf("★**************************************************************★\n");382 printf("按任意键继续!\n");383 getch();//暂停函数,所在头文件 384 system("cls");//清屏函数385 }