C语言迷宫求解

秒速五厘米 2022-08-08 11:47 141阅读 0赞

虽然这个程序很小，但是为了实现它却着实是花了一番工夫呢，呵呵

//定义状态常量  
\#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表示墙 
\*/ 
int maze\[8\]\[8\] = \{ 
    1,1,0,1,1,1,0,1, 
    1,1,0,1,1,1,0,1, 
    1,1,1,1,0,0,1,1, 
    1,0,0,0,1,1,1,1, 
    1,1,1,0,1,1,1,1, 
    1,0,1,1,1,0,1,1, 
    1,0,0,0,1,0,0,1, 
    0,1,1,1,1,1,1,1 
\};

//定义栈元素类型  
typedef struct MStackElem  
\{  
    int x;//x坐标  
    int y;//y坐标  
    int val;//maze\[x\]\[y\]的值  
\}MStackElem;

//定义栈  
typedef struct \{  
    MStackElem \* base;  
    MStackElem \* top;  
    int stackSize;  
\}MStack;

//=============Stack的实现========================

//初始化栈-------构造一个空栈  
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 space! 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+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; //因为是重新分配了空间,所以base的值其实已经改变,所以top的值也就相应的改变,才能指向新的迷宫栈  
       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) \{  
//若栈不为空,则删除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) \{//这里不能传path的地址,否则在遍历过程中它的top值就真的被改了 !!  
    int flag = 1;  
    while(path.top != path.base)  
    \{  
       MStackElem e = \*(path.top - 1);  
       if (e.x == cur.x&& e.y == cur.y)  
       \{  
        flag = 0;  
       \}  
       //每循环一次令头指针下移一个位置  
       (path.top)--;  
    \}  
    return flag;  
\}

//获得东面相邻的位置  
MStackElem getEast(MStackElem cur) \{  
           if(cur.y != 7) \{//当y==7时已到了迷宫右边界,不能再向东(右)行了  
                cur.y += 1;  
                cur.val = maze\[cur.x\]\[cur.y\];  
           \}  
           return cur;// 当y==7时返回的是它本身  
\}  
//获得南面相邻的位置  
MStackElem getSouth(MStackElem cur) \{  
           if(cur.x != 7) \{//当x==7时已到了迷宫下边界,不能再向南(下)行了  
                cur.x += 1;  
                cur.val = maze\[cur.x\]\[cur.y\];  
           \}  
           return cur;// 当x==7时返回的是它本身  
\}  
//获得西面相邻的位置  
MStackElem getWest(MStackElem cur) \{  
           if(cur.y != 0) \{//当y==0时已到了迷宫左边界,不能再向西(左)行了  
                cur.y -= 1;  
                cur.val = maze\[cur.x\]\[cur.y\];  
           \}  
           return cur;// 当y==0时返回的是它本身  
\}  
//获得北面相邻的位置  
MStackElem getNorth(MStackElem cur) \{  
     if(cur.x != 0) \{//当cur.x==0时表示在迷宫的上边界,不能再向北(上)行了  
        cur.x -= 1;  
        cur.val = maze\[cur.x\]\[cur.y\];  
     \}  
     return cur;// 当cur.x==0时返回的还是它本身  
\}

//获得下一个可通行的位置,按东南西北的方向试探  
MStackElem getNext(MStackElem cur) \{  
MStackElem next;  
next.x = next.y=next.val = -1;  
if(getEast(cur).val != 0 && unPass(path,getEast(cur))) \{  
   next = getEast(cur);  
\}  
else if(getSouth(cur).val != 0 && unPass(path,getSouth(cur))) \{  
   next = getSouth(cur);  
\}  
else if(getWest(cur).val != 0 && unPass(path,getWest(cur))) \{  
   next = getWest(cur);  
\}  
else if(getNorth(cur).val != 0 && unPass(path,getNorth(cur))) \{  
   next = getNorth(cur);  
\}  
//如果当前位置的四面或为墙或已走过,则返回的next的val值为-1  
return next;  
\}

int getMazePath()\{//获得迷宫路径的函数

MStackElem start,end,cur;  
    start.x = 0;  
    start.y = 0;  
    start.val = maze\[start.x\]\[start.y\];  
    end.x = 7;  
    end.y = 7;  
    end.val = maze\[end.x\]\[end.y\];  
     
    cur = start; //设定当前为位置为"入口位置"  
    //没有重载=运算符,可以这样用吗,结果对吗?试试吧:  
    /\*                                                
    printf("%d",cur.x);  
    printf("%d",cur.y);  
    printf("%d",cur.val);                                                  
    \*/  
    //恩,结果是正确的,即可以通过cur=start来把start的值赋给cur.  
    //对了,想起来了,记得以前在学C++的复制构造函数时书上好像说过, 用=(等号)复制类对象时系统会调用由系统提供的复制的构造函数什么的,  
    //唉,记不清了,还是基础不扎实啊,以后可不能轻视基础了@\_@ ...  
     
    do  
    \{                                                   
        if (unPass(path,cur)) \{//如果当前位置未曾走到过  
            push(&realPath,cur);  
            push(&path,cur);  
            cur = getNext(cur);  
            if (cur.x == end.x && cur.y == end.y) \{ //到达出口了,则跳出循环,并返回true  
               //把出口结点放入路径中  
                push(&realPath,cur);  
                push(&path,cur);  
                //直接跳出函数(而不只是跳出这个循环 )  
                return true;  
            \}  
            else if(cur.val == -1) \{//当前位置的四面或为墙或已走过  
                 //删除真实路径的栈顶元素  
                 pop(&realPath);  
                 cur = getTop(&realPath);//令cur指向栈顶元素  
             \}  
        \}  
       else \{//如果当前位置已经走过,说明原来测试的方向不对,现在尝试其它方向  
            cur = getNext(cur);  
            if (cur.val == -1) \{//仍不通,删除真实路径的栈顶元素  
               pop(&realPath);  
               cur = getTop(&realPath);//令cur指向栈顶元素  
            \}  
       \}  
    \} while (cur.x != end.x || cur.y != end.y);  
\}

//打印迷宫路径  
void printMazePath(MStack \*s) \{//为了安全,这里不传MStack的地址,以防在遍历的过程中把它们的top或base的值也修改了  
     /\*注:这种方法实际是倒序打印出路径,让人看着别扭  
     while (s->top != s->base) \{  
       MStackElem e = \*(s->top-1);  
       printf("maze\[%d\]\[%d\]----->",e.x,e.y);  
       (s->top)--;  
    \}  
    \*/

//所以为了按实际顺序打印路径,则应"倒序遍历这个栈 '  
     MStackElem e; 
     while (s->base < (s->top-1)) \{ 
      e = \*(s->base);//先指向栈底元素,以后依次向上增1 
       printf("maze\[%d\]\[%d\]----->",e.x,e.y); 
       (s->base)++; 
     \} 
     //最后一个结点没有后继,所以不再输出"------>" 
     e = \*(s->base); 
     printf("maze\[%d\]\[%d\]",e.x,e.y); 
\}

main()\{  
      //初始化栈  
    initStack(&realPath);  
    initStack(&path);

//求解路径  
    getMazePath();

//打印路径

printf("The path of through the maze is:/n/n");  
    printMazePath(&realPath);  
    getchar();  
\}