离散数学 迷宫最短路径

迷宫最短路径⒈问题描述从一个迷宫的入口到出口找出一条最短路经。

用一个二维数组MAZE(1：m，1：n)模拟迷宫，数组元素为0表示该位置可以通过，数组元素为1表示该位置不可以通行。

MAZE(1，1)和MAZE(m，n)分别为迷宫的入口和出口。

⒉基本要求(1)输入数据a.输入迷宫的大小m行和n列，两者为整数b.由随机数产生0或1，建立迷宫。

(2)输出数据首先输出模拟迷宫的二维数组，若存在最短路经，则由出口回朔到入口打印这一条路径，如下所示：(m，n)，……， (I，j)，……， (1，1)如无通道，则打印：THERE IS NO PATH.#include<time.h>#define OVERFLOW -2#define ERROR 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 <stdio.h>#include <stdlib.h>/*初始化迷宫,1表示通道,0表示墙*/typedef struct MStackElem{int x;int y;int val;}MStackElem;typedef struct {MStackElem * base;MStackElem * top;int stackSize;}MStack;void 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 spac e! exit now. ");exit(OVERFLOW);}s->top = s->base;s->stackSize = STACK_INIT_SIZE;}void push(MStack *s,MStackElem e) {if (s->top - s->base >= s->stackSize) {s->base = (MStackElem *)realloc(s->base, (STACK_INIT_SIZE+STACKINCREMEN T) * sizeof(MStackElem));if (!s->base) {printf("in push()...Failed to realloc the MStack ,no enough space! exi t now. ");exit(OVERFLOW);}s->top = s->base + s->stackSize;s->stackSize += STACKINCREMENT;}*(s->top++) = e;}MStackElem 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 flag = 1;while(path.top != path.base){MStackElem e = *(path.top - 1);if (e.x == cur.x&& e.y == cur.y)回复2楼2010-01-15 19:07举报 |吧友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.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 getNorth(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);}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(cur,*maze,n);}return next;}int getMazePath(int *maze,int n){回复3楼2010-01-15 19:07举报 |吧友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) {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); }。