离散数学-迷宫最短路径

1、迷宫最短路径问题描述 从一个迷宫的入口到出口找出一条最短路经。用一个二维数组MAZE(1：m，1：n)模拟迷宫，数组元素为0表示该位置可以通过， 数组元素为1表示该位置不可以通行。MAZE(1，1)和MAZE(m，n)分别为迷宫的入口和出口。基本要求输入数据输入迷宫的大小m行和n列，两者为整数由随机数产生0或1，建立迷宫。输出数据首先输出模拟迷宫的二维数组，若存在最短路经，则由出口回朔到入口打印这一条路径，如下所示： (m，n)， ， (I，j)， ， (1，1)如无通道，则打印： THERE IS NO PATH.#include#define OVERFLOW -2#define ERRO

2、R 0#define NULL 0#define true 1#define TRUE 1#define false 0#define FALSE 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#include #include /*初始化迷宫,1表示通道,0表示墙*/typedef struct MStackElem int x; int y; int val;MStackElem;typedef struct MStackElem * base; MStackElem * top; int stackSize;MStack;voi

3、d initStack(MStack *s) s-base = (MStackElem *)malloc(STACK_INIT_SIZE * sizeof(MStackElem); if (!s-base) printf(in initStack().Failed to initalize the MStack ,no enough space! exit now. ); exit(OVERFLOW); s-top = s-base; s-stackSize = STACK_INIT_SIZE;void push(MStack *s,MStackElem e) if (s-top - s-ba

4、se = s-stackSize) s-base = (MStackElem *)realloc(s-base, (STACK_INIT_SIZE+STACKINCREMENT) * sizeof(MStackElem); if (!s-base) printf(in push().Failed to realloc the MStack ,no enough space! exit now. ); exit(OVERFLOW); s-top = s-base + s-stackSize; s-stackSize += STACKINCREMENT; *(s-top+) = e;MStackE

5、lem getTop(MStack *s) if (s-top = s-base) printf(in getTop(),empty stack! exit now. ); exit(ERROR);else return *(s-top - 1);void pop(MStack *s) if (s-top = s-base) printf(in pop(),empty stack! exit now. ); exit(ERROR); else -(s-top); MStack realPath,path;int unPass(MStack path,MStackElem cur) int fl

6、ag = 1; while(path.top != path.base) MStackElem e = *(path.top - 1); if (e.x = cur.x& e.y = cur.y)HYPERLINK /p/696325105#回复2楼2010-01-15 19:07HYPERLINK /p/696325105#举报 |吧友125.77.120.* flag = 0; (path.top)-; return flag;MStackElem getEast(MStackElem cur,int *maze,int n) if(cur.y != 7) cur.y += 1; cur.

7、val = *(maze+cur.x*n+cur.y); return cur; MStackElem getSouth(MStackElem cur,int *maze,int n) if(cur.x != 7) cur.x += 1; cur.val = *(maze+cur.x*n+cur.y); return cur;MStackElem getWest(MStackElem cur,int *maze,int n) if(cur.y != 0) cur.y -= 1; cur.val = *(maze+cur.x*n+cur.y); return cur;MStackElem get

8、North(MStackElem cur,int *maze,int n) if(cur.x != 0) cur.x -= 1; cur.val = *(maze+cur.x*n+cur.y); return cur;MStackElem getNext(MStackElem cur,int *maze,int n) MStackElem next;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

9、);else if(getSouth(cur,*maze,n).val != 0 & unPass(path,getSouth(cur,*maze,n) next = getSouth(cur,*maze,n);else if(getWest(cur,*maze,n).val != 0 & unPass(path,getWest(cur,*maze,n) next = getWest(cur,*maze,n);else if(getNorth(cur,*maze,n).val != 0 & unPass(path,getNorth(cur,*maze,n) next = getNorth(cu

10、r,*maze,n);return next;int getMazePath(int *maze,int n)HYPERLINK /p/696325105#回复3楼2010-01-15 19:07HYPERLINK /p/696325105#举报 |吧友125.77.120.* MStackElem start,end,cur; start.x = 0; start.y = 0; start.val = *(maze+start.x*n+start.y); end.x = 7; end.y = 7; end.val = *(maze+end.x*n+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); return true; else if(cur.val = -1) po