C语言迷宫的解源码

题目介绍：
用二维数组表示迷宫，1表示通顺路口，2表示搜索过的，0表示障碍路口，采用递归、堆栈的方式求迷宫出路的解并输出。

第一部分使用递归求解
为了数据的简单化，不对路口进行数据结构化，将用一个简单的int类型数组来表示迷宫
因为每一个路口的四个方向相对于当前路口的位移都是一样的，这样可以用一个int类型
二位数据表示四个方向的相对于当前位置的位移，以顺时针东、南，、西、北储存

第一个方法是采用递归的方式求解，通过探测下一个路口的方式来求解。
第二种则用堆栈求解，这里涉及到栈数据结构的使用，栈的基本操作代码略过

两种代码主要解法如下：

1.
int MAZE(int x, int y) {
    //将越界路口跳出
    if(x<0||x>m||y<0||y>n) {
        return 0;
    }
    int a,b;
    int tag = 0;
    //迷宫出口
    if(x==8 && y==7)
        return 1;
 
    //试探相邻的4个路口
    for(int i= 0; i<4; i++) {
        a= x+ move[i][0];
        b= y+ move[i][1];
 
 
        //如果路口通顺且没搜索过则进入该路口，否则什么都不做
        if(maze[a][b]==1) {
 
            maze[a][b]= 2;//(a,b)上的值改成2表示走过的路
            //进入路口
            tag= MAZE(a, b);
            //判断是否找到出口用于输出路径
            if(tag) {
 
                printf("(%d,%d)←",a,b);
                return 1;
            }
        }
    }//end for
    return 0;
}

 
void getPass() {
 
    SeqStack s; //堆栈
    StackInitiate(&s);         //堆栈初始化
    Stack ss;
    int a=0,b=0;       //a,b表示当前搜索的迷宫位置，当前是入口
 
    ss.x=a;
    ss.y=b;
    ss.condition=mazee[a][b]=2;
    StackPush(&s,ss);
 
    while(StackNotEmpty(s)) {      //将堆栈为空设置成停止循环的条件，也意味着没有通路；
 
        StackTop(s,&ss);  //获取当前位置
 
        //下个路口的探索
        for(int i= 0; i<4; i++) {
 
            a= ss.x+ move[i][0];
            b= ss.y+ move[i][1];
            //如果不越界，进入下一个方向
            if(a>=0&&a<m&&b>=0&&b<n) {
 
                //如果通顺,进入路口，入栈，否则什么都不做，搜索另一个方向
                if(mazee[a][b]==1) {
                    mazee[a][b]=2;
                    ss.condition=mazee[a][b];
                    ss.x=a;
                    ss.y=b;
                    StackPush(&s,ss);
                    break;
 
                }//end if
            }//end if
            if(i==3) {
                StackPop(&s,&ss);      //但搜索到第四个方向且该方向的路口不通，出栈
            }
        }//end for
 
        //迷宫出口
        if(a==8&&b==7)break;     //但搜索到出口跳出
    }//end while
 
 
    if(!StackNotEmpty(s))printf("该迷宫没有通路\n");
    else {
        while(StackNotEmpty(s)) {
            StackPop(&s,&ss);
            printf("(%d,%d)←",ss.x,ss.y);
        }//end while
    }//end else
}

客户端（主函数）显示结果：

int main() {
 
 
    //堆栈求迷宫通路
    printf("堆栈求迷宫的通路：\n");
    getPass();
    printf("\n\n\n\n");
    
    //递归求所有通路，按一定方向顺序进行搜索能得到一条路径，反过来想的话，用不同方向顺序进行搜索能得到不同路径，除非只有一条通路
    //调用MAZE,每调用依次必须对迷宫进行初始化
    printf("递归求迷宫的通路：\n");
    MAZE(0,0);
    //迷宫入口
    printf("(0,0)←入口\n");
 
    system("pause");
}