迷宫最短路径
⒈问题描述
从一个迷宫的入口到出口找出一条最短路经。用一个二维数组MAZE(1：m，1：n)模拟迷宫，数组元素为0表示该位置可以通过，数组元素为1表示该位置不可以通行。MAZE(1，1)和MAZE(m，n)分别为迷宫的入口和出口。
⒉基本要求
输入数据
输入迷宫的大小m行和n列，两者为整数
由随机数产生0或1，建立迷宫。
输出数据
首先输出模拟迷宫的二维数组，若存在最短路经，则由出口回朔到入口打印这一条路径，如下所示：
(m，n)，……，(I，j)，……，(1，1)
如无通道，则打印：
THEREISNOPATH.
#include#defineOVERFLOW-2#defineERROR0#defineNULL0#definetrue1#defineTRUE1#definefalse0#defineFALSE0#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#include#include/初始化迷宫,1表示通道,0表示墙/typedefstructMStackElem{intx;inty;intval;}MStackElem;typedefstruct{MStackElembase;MStackElemtop;intstackSize;}MStack;voidinitStack(MStacks){s->base=(MStackElem)malloc(STACK_INIT_SIZEsizeof(MStackElem));if(!s->base){printf("ininitStack()...FailedtoinitalizetheMStack,noenoughspace!exitnow.");exit(OVERFLOW);}s->top=s->base;s->stackSize=STACK_INIT_SIZE;}voidpush(MStacks,MStackEleme){if(s->top-s->base>=s->stackSize){s->base=(MStackElem)realloc(s->base,(STACK_INIT_SIZE+STACKINCREMENT)sizeof(MStackElem));if(!s->base){printf("inpush()...FailedtorealloctheMStack,noenoughspace!exitnow.");exit(OVERFLOW);}s->top=s->base+s->stackSize;s->stackSize+=STACKINCREMENT;}(s->top++)=e;}MStackElemgetTop(MStacks){if(s->top==s->base){printf("ingetTop(),emptystack!exitnow.");exit(ERROR);}else{return(s->top-1);}}voidpop(MStacks){if(s->top==s->base){printf("inpop(),emptystack!exitnow.");exit(ERROR);}else{--(s->top);}}MStackrealPath,path;intunPass(MStackpath,MStackElemcur){intflag=1;while(path.top!=path.base){MStackEleme=(path.top-1);if(e.x==cur.x&&e.y==cur.y)
回复
2楼
2010-01-1519:07
举报|
吧友125.77.120.
{flag=0;}(path.top)--;}returnflag;}MStackElemgetEast(MStackElemcur,intmaze,intn){if(cur.y!=7){cur.y+=1;cur.val=(maze+cur.xn+cur.y);}returncur;}MStackElemgetSouth(MStackElemcur,intmaze,intn){if(cur.x!=7){cur.x+=1;cur.val=(maze+cur.xn+cur.y);}returncur;}MStackElemgetWest(MStackElemcur,intmaze,intn){if(cur.y!=0){cur.y-=1;cur.val=(maze+cur.xn+cur.y);}returncur;}MStackElemgetNorth(MStackElemcur,intmaze,intn){if(cur.x!=0){cur.x-=1;cur.val=(maze+cur.xn+cur.y);}returncur;}MStackElemgetNext(MStackElemcur,intmaze,intn){MStackElemnext;next.x=next.y=next.val=-1;if(getEast(cur,maze,n).val!=0&&unPass(path,getEast(cur,maze,n))){next=getEast(cur,maze,n);}elseif(getSouth(cur,maze,n).val!=0&&unPass(path,getSouth(cur,maze,n))){next=getSouth(cur,maze,n);}elseif(getWest(cur,maze,n).val!=0&&unPass(path,getWest(cur,maze,n))){next=getWest(cur,maze,n);}elseif(getNorth(cur,maze,n).val!=0&&unPass(path,getNorth(cur,maze,n))){next=getNorth(cur,maze,n);}returnnext;}intgetMazePath(intmaze,intn){
回复
3楼
2010-01-1519:07
举报|
吧友125.77.120.
MStackElemstart,end,cur;start.x=0;start.y=0;start.val=(maze+start.xn+start.y);end.x=7;end.y=7;end.val=(maze+end.xn+end.y);cur=start;printf("%d",cur.x);printf("%d",cur.y);printf("%d",cur.val);do{if(unPass(path,cur)){push(&realPath,cur);push(&path,cur);cur=getNext(cur,maze,n);if(cur.x==end.x&&cur.y==end.y){push(&realPath,cur);push(&path,cur);returntrue;}elseif(cur.val==-1){pop(&realPath);cur=getTop(&realPath);}}else{cur=getNext(cur,maze,n);if(cur.val==-1){pop(&realPath);cur=getTop(&realPath);}}}while(cur.x!=end.x||cur.y!=end.y);}
|
|
