c语言回溯法破解迷宫

《c语言回溯法破解迷宫》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、#include#include//定义栈structTNode{structNode*top;}TNode;typedefstructTNode*TN;structNode{intx;inty;structNode*next;}Node;typedefstructNode*N;//压栈voidPush(TNtn,intxx,intyy){Nq;q=(N)malloc(sizeof(Node));q->x=xx;q->y=yy;q->next=tn->top;tn->top=q;}//出栈voidOut(TNtn){Nq;

2、if(tn->top==NULL)return;q=tn->top;tn->top=tn->top->next;free(q);}//回溯法过迷宫voidPast(intmaze[10][10],intdirection[8][2],intx1,inty1,intx2,inty2){TNtn;intmark[10][10]={//0123456789{0,0,0,0,0,0,0,0,0,0},//0{0,0,0,0,0,0,0,0,0,0},//1{0,0,0,0,0,0,0,0,0,0},//2{0,0,0,0,0,0,0,0,0,0},//3{0,0,0,

3、0,0,0,0,0,0,0},//4{0,0,0,0,0,0,0,0,0,0},//5{0,0,0,0,0,0,0,0,0,0},//6{0,0,0,0,0,0,0,0,0,0},//7{0,0,0,0,0,0,0,0,0,0},//8{0,0,0,0,0,0,0,0,0,0},//9};tn=(TN)malloc(sizeof(TNode));//创建栈tn->top=NULL;Push(tn,x1,y1);//压入入口坐标mark[x1][y1]=1;while(tn->top!=NULL){intm,n,hang,lie,i=0;m=tn->top->x

4、;n=tn->top->y;//循环方向数组,探四个方向for(;i<8;){hang=m+direction[i][0];lie=n+direction[i][1];if(hang==x2&&lie==y2){Push(tn,hang,lie);printf("迷宫已破解！！！路径是：");while(tn->top!=NULL){if(tn->top->x==x2&&tn->top->y==y2)maze[tn->top->x][tn->top->y]=4;elsemaze[tn->top->x][tn->top->y]=3;Out(tn);}Pr

5、int(maze);return;}if(mark[hang][lie]!=1&&maze[hang][lie]==0){mark[hang][lie]=1;Push(tn,hang,lie);m=hang;n=lie;i=-1;}i+=1;}Out(tn);}printf("找不到通路，迷宫无法走出去！！！");}//输出结果★voidPrint(intarray[10][10]){inti,j;for(i=0;i<10;i++){for(j=0;j<10;j++){if(array[i][j]==3)printf("￥");elseif(array[i

6、][j]==4)printf("★");elseprintf("%5d",array[i][j]);}printf("");}printf("");}intmain(){//定义迷宫数组intmaze[10][10]={//0123456789{1,0,1,1,1,1,1,1,1,1},//0{1,0,1,1,1,0,0,0,0,1},//1{1,0,0,0,1,0,1,0,0,1},//2{1,0,1,0,0,1,1,0,1,1},//3{1,0,1,1,1,0,1,1,0,1},//4{1,0,1,1,1,0,1,1,0,1},//5{1,0,1,

7、1,1,0,1,1,0,1},//6{1,0,1,0,1,1,0,1,0,1},//7{1,0,0,1,0,0,1,1,0,1},//8{1,1,1,1,1,1,1,1,1,0},//9};//定义方向数组intdirection[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1},};printf("迷宫数组是：");Print(maze);printf("开始破解......");Past(maze,direction,0,1,9,9);getch();}