问题引出

有的时候，除了只有一条出口的迷宫外，我们还会遇到多出口迷宫求解问题，即


  
有多条出口的迷宫，迷宫内部各路径不交叉，不成环，求其中最短的一条路径


例如： 

 

关于单出口的简单迷宫求解，大家可以参考


  
简单迷宫求解


解题思路

因为迷宫中存在多条路径，所以这次我们采用自己构造栈的方式进行求解


构建两个栈，一个栈为 cur_path，保存当前走过的路径，另一个栈为 short_path，保存最短的路径
判断当前该点是否能落脚，不能落脚直接返回 
标记当前点，并且入栈到cur_path
进入循环，先拿到当前的栈顶元素(该元素一定合法)
判断当前点是否为出口 

是出口，将 两个栈中的元素进行比较  

如果cur_path保存的路径比short_path中保存的路径长，就将当前 cur_path 路径 保存至short_path中 
否则，继续寻找其他路径，并且当前栈顶元素，进行回溯
如果不是出口，按顺时针方向依次取相邻点，并判定他们是否能落脚，如果可以，入栈，进入下一轮循环
四个点都不能落脚，出栈当前栈顶元素，回溯


方法实现

这里我们要用到栈的一些操作，对于栈的概念和操纵还不太理解的可以移步


  
顺序表实现的数据结构栈


maze.h

#include "seqstack.h"
#include <stdio.h>

// 迷宫的长宽
#define ROW 10 // 行
#define COL 10 // 列

typedef struct Maze {
    int map[COL][ROW];
} Maze;

// 创建迷宫
void createMaze(Maze* maze) {
    int tmp[COL][ROW] = {
        { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0 },
        { 0, 1, 1, 1, 1, 0, 1, 1, 1, 0 },
        { 0, 1, 0, 0, 1, 0, 1, 0, 1, 0 },
        { 0, 1, 0, 0, 1, 0, 1, 0, 1, 0 },
        { 0, 1, 0, 0, 1, 0, 1, 0, 1, 0 },
        { 1, 1, 1, 0, 1, 1, 1, 0, 1, 1 },
        { 0, 0, 1, 0, 0, 0, 0, 0, 1, 0 },
        { 0, 0, 1, 1, 1, 0, 0, 0, 1, 0 },
        { 0, 0, 0, 0, 1, 0, 1, 1, 1, 0 },
        { 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 }
    };
    int i = 0;

    for( ; i < COL; i++) {
        int j = 0;
        for( ; j < ROW; j++) {
            maze->map[i][j] = tmp[i][j];
        }
    }
}

// 打印迷宫
void printMaze(Maze maze) {
    int i = 0;

    // 装饰性打印
    printf(" +");
    for( ; i < ROW*2; i++) {
        printf("-");
    }
    printf("-+");
    printf("\n");

    // 打印开始
    for( i = 0; i < COL; i++) {
        int j = 0;
        printf(" | ");
        for( ; j < ROW; j++) {
            printf("%d ", maze.map[i][j]);
        }
        printf("|\n");
    }

    // 装饰性打印
    printf(" +");
    for( i = 0; i < ROW*2; i++) {
        printf("-");
    }
    printf("-+\n");

}

// 判断当前点是否能够落脚
int Canstay(Maze* maze, Coordinates pos) {
    // 越界
    if(pos.row>=0 && pos.row<ROW && pos.col>=0 && pos.col<COL) {
        if(maze->map[pos.col][pos.row] == 1) {
            return 1;
        }
        return 0;
    }
    return 0;
}

// 将当前点进行标记
void Mark(Maze* maze, Coordinates pos) {
    maze->map[pos.col][pos.row] = 2;
}

// 是否为出口
int isExit(Maze* maze, Coordinates entry, Coordinates pos) {
    if((pos.row==entry.row) && (pos.col==entry.col)) {
        return 0;
    }
    if(pos.row==0 || pos.row==ROW-1 || pos.col==0 || pos.col==COL-1) {
        return 1;
    }
    return 0;
}

// 打印路径
void printPath(SeqStack stack) {
    Datatype value;
    while(SeqStackTop(&stack, &value)) {
        printf("(%d, %d)\n", value.row, value.col );
        SeqStackPop(&stack);
    }
}

// 比较两个栈长度，s1 <= s2，返回 <=0，否则， >0
int compareStack(SeqStack stack1, SeqStack stack2) {
    Datatype value;
    int ret = 0;
    int count1 = 0;
    int count2 = 0;
    while(ret=SeqStackTop(&stack1, &value)) {
        SeqStackPop(&stack1);
        count1++;
    }
    while(ret=SeqStackTop(&stack2, &value)) {
        SeqStackPop(&stack2);
        count2++;
    }
    return count1-count2;

} 

// 将 src 栈的所有元素拷贝到 dst 栈中 
void cloneStack(SeqStack* dest, SeqStack* src) {
    // 由于是顺序表构成的栈，所以首先释放 dest 空间
    SeqStackDestroy(dest);
    // 创建新空间
    dest->size = src->size;
    dest->capacity = src->capacity;
    dest->data = malloc(sizeof(SeqStack) * src->capacity);
    int i = 0;
    for(i = 0; i < src->size; i++) {
        dest->data[i] = src->data[i];
    }
}   

void getMazePath(Maze* maze, Coordinates entry) {
    // 构建两个栈，一个栈为 cur_path，保存当前走过的路径，另一个栈为 short_path，保存最短的路径
    SeqStack cur_path;
    SeqStack short_path;
    SeqStackInit(&cur_path);
    SeqStackInit(&short_path);
    // 判断当前该点是否能落脚，不能落脚直接返回 
    if(!Canstay(maze, entry)) {
        return; 
    }
    // 标记当前点，并且入栈到cur_path
    Mark(maze, entry);
    SeqStackPush(&cur_path, entry);
    int ret = 1;    
    while(ret == 1) {
        // 进入循环，先拿到当前的栈顶元素(该元素一定合法)
        Coordinates cur;
        ret = SeqStackTop(&cur_path, &cur);

        // 判断当前点是否为出口，是出口就找到了一条路 
        if(isExit(maze, entry, cur) == 1) {
            // 是出口，将 两个栈中的元素进行比较 
            // 如果short_path < cur_path，返回 <0，否则 >0
            int compare = compareStack(short_path, cur_path);           
            // 第一次 short_path 为空
            Datatype value;
            if(SeqStackTop(&short_path, &value) == 0) {
                cloneStack(&short_path, &cur_path); 
                printf("找到一条路径[%d, %d]\n", cur.col, cur.row);
            }
            // 如果cur_path保存的路径比short_path中保存的路径长，就将当前 cur_path 路径 保存至short_path中 
            if(compare < 0) {
                cloneStack(&short_path, &cur_path); 
                printf("找到一条更短的路径[%d, %d]\n", cur.col, cur.row);

            } else {
                // 否则，继续寻找其他路径
                printf("又找到一条路径[%d, %d]\n", cur.col, cur.row);
            }
            // 出栈当前栈顶元素，回溯
            SeqStackPop(&cur_path);
        }       
        // 如果不是，按顺时针方向依次取相邻点，并判定他们是否能落脚，如果可以，入栈，进入下一轮循环
        // 上
        Coordinates up;
        up.col = cur.col-1;
        up.row = cur.row;

        if(Canstay(maze, up)) {
            Mark(maze, up);
            SeqStackPush(&cur_path, up);
            continue;
        }

        //  右 
        Coordinates right;
        right.col = cur.col;
        right.row = cur.row+1;

        if(Canstay(maze, right)) {
            Mark(maze, right);
            SeqStackPush(&cur_path, right);
            continue;
        }


        //  下 
        Coordinates down;
        down.col = cur.col+1;
        down.row = cur.row;

        if(Canstay(maze, down)) {
            Mark(maze, down);
            SeqStackPush(&cur_path, down);
            continue;
        }

        // 左 
        Coordinates left;
        left.col = cur.col;
        left.row = cur.row-1;

        if(Canstay(maze, left)) {
            Mark(maze, left);
            SeqStackPush(&cur_path, left);
            continue;
        }

        // 四个点都不能落脚，出栈当前栈顶元素，回溯
        SeqStackPop(&cur_path);
    }
    // 打印路径
    printPath(short_path);
}

int main() {
    Maze maze;
    Coordinates entry;
    entry.col = 0;
    entry.row = 1;
    // 创建迷宫
    createMaze(&maze);
    // 打印迷宫
    printMaze(maze);
    // 求解迷宫线路
    getMazePath(&maze, entry);

    printMaze(maze);
}

求解多出口迷宫的最短路径，是在基于求解简单迷宫是否存在路径的问题的基础上的一个提高。我们首先需要认识到的是，不论是求解简单迷宫问题，还是复杂迷宫的问题，我们都需要基于栈，使用回溯法来解决问题。
首先，我们先来定义一个多出口的迷宫：
                       
图中0表示墙，即无法落脚；1表示可以落脚；之后我们会用2来标记走过的路。
我们默认出口为四个边界上的点。若入口也为边界点，则出口与入口不能重合。
maze.h：
#pragma once
#include <stdio.h> 
#include<stdlib.h>
#include<stddef.h>

#define MAX_ROW 6
#define MAX_COL 6

typedef struct Point{
    int row;
    int col;
}Point;
typedef Point SeqStackType;

typedef struct SeqStack{
    SeqStackType *data;
    size_t size;
    size_t capacity;
}SeqStack;
typedef struct Maze{
    int map[MAX_ROW][MAX_COL];
}Maze;
maze.c：
#include "maze.h"
 
int map[MAX_ROW][MAX_COL]={
    {0,1,0,0,0,0},
    {0,1,1,1,0,0},
    {0,1,0,1,1,1},
    {1,1,1,0,0,0},
    {0,0,1,0,0,0},
    {0,0,1,0,0,0}
};

void MazeInitShortPath(Maze* maze){//初始化
    if(maze == NULL)
        return;
    size_t i = 0;
    for(;i < MAX_ROW;i++){
        size_t j = 0;
        for(;j < MAX_COL;j++){
            maze->map[i][j] = map[i][j];
        }
    }
    return;
}

void SeqStackDebugPrint(SeqStack* stack,const char* msg){//走过的路径中每一个点的打印
    printf("%s\n",msg);
    if(stack == NULL)
        return;
    size_t i = 0;
    for(;i < stack->size;i++){
        printf("(%d,%d)\n",stack->data[i].row,stack->data[i].col);
    }
        printf("\n");
        return;
}

void MazePrint(Maze* maze){//迷宫的打印
    if(maze == NULL)
        return;
    size_t i = 0;
    for(;i < MAX_ROW;i++){
        size_t j = 0;
        for(;j < MAX_COL;j++)
            printf("%2d ",maze->map[i][j]);
        printf("\n");
    }
    return;
}
    
int CanStay(Maze* maze,Point pt){//判断当前点是否能落脚
    if(maze == 0)
        return 0;
    if(pt.row < 0 || pt.row >= MAX_ROW || pt.col < 0 || pt.col >= MAX_COL){//迷宫边界外，不能落脚
        return 0;
    }
    int value = maze->map[pt.row][pt.col];
    if(value == 1){//边界内，且可落脚
        return 1;
    }
    return 0;
}

void Mark(Maze* maze,Point cur){//标记走过的路径
    maze->map[cur.row][cur.col] = 2;
}

int IsExit(Maze* maze,Point cur,Point entry){//判断当前点是否为出口
    (void)maze;
    //1.判断当前点是不是入口，若为入口，则不是出口
    if(cur.row == entry.row && cur.col == entry.col){
        return 0;
    }
    //2.如果当前点在地图边界上，说明是出口
    if(cur.row == 0 || cur.row == MAX_ROW-1 || cur.col == 0 || cur.col == MAX_COL-1){
        return 1;
    }
    return 0;
}

void SeqStackAssgin(SeqStack* from,SeqStack* to){//将from中的数据全部拷贝至to中
    //释放to中的原有内存
    SeqStackDestroy(to);
    //根据from中的元素个数确定内存申请的大小，给to重新申请一个足够的内存
    to->size = from->size;
    to->capacity = from->capacity;
    to->data = (SeqStackType*)malloc(to->capacity * sizeof(SeqStackType));
    //再进行数据拷贝
    size_t i = 0;
    for(;i < from->size;i++){
        to->data[i] = from->data[i];
    }
}

void _GetShortPath(Maze* maze,Point cur,Point entry,SeqStack* cur_path,SeqStack* short_path){//GetShortPath的辅助函数
    printf("cur:(%d,%d)\n",cur.row,cur.col);
    //1.判断当前点能否落脚
    if(!CanStay(maze,cur)){
        return;
    }
    //2.若能落脚，给当前位置做一个标记
    //同时将当前点插入到cur_path
    Mark(maze,cur);
    SeqStackPush(cur_path,cur);
    //3.若当前点为出口，说明找到了一条出口
    if(IsExit(maze,cur,entry)){
        printf("找到了一条路径\n");
        if(cur_path->size < short_path->size || short_path->size == 0){
            //将当前路径与short_path中的路径对比，若当前路径比short_path短或short_path本身为空栈，则用当前路径替换short_path
            SeqStackAssgin(cur_path,short_path);
            printf("找到了一条相对较短的路径\n");
        }
        //若当前路径没有比short_path短，就尝试找其他路径
        SeqStackPop(cur_path);
        return;
    }
    //4.若当前点不是出口，则按顺时针方向探测四个相邻的点，递归式调用函数自身，递归式更新cur节点
    //（每次递归时，cur都是下一次要走的点，这个点能否落脚，交给递归函数作判断）
    Point up = cur;
    up.row -= 1;
    _GetShortPath(maze,up,entry,cur_path,short_path);

    Point right = cur;
    right.col += 1;
    _GetShortPath(maze,right,entry,cur_path,short_path);

    Point down = cur;
    down.row += 1;
    _GetShortPath(maze,down,entry,cur_path,short_path);

    Point left = cur;
    left.col -= 1;
    _GetShortPath(maze,left,entry,cur_path,short_path);
    
    //若四个方向都递归的探测过了，则可进行出栈，同时回溯到上一个点
    SeqStackPop(cur_path);
    return;
}

void GetShortPath(Maze* maze,Point entry){
    SeqStack cur_path;
    SeqStack short_path;
    SeqStackInit(&cur_path);
    SeqStackInit(&short_path);
    _GetShortPath(maze,entry,entry,&cur_path,&short_path);
    SeqStackDebugPrint(&short_path,"最短路径为");
    return;
}
通过代码我们可以认识到，由于多出口迷宫存在着多条路径，所以我们需要定义两个栈，一个栈中存放着当前走过的路径的数据，另一个栈中存放着最短路径的数据。每找到一条路径，就将当前路径的长度与最短路径的长度作比较，若存放最短路径的栈为空栈，或者当前路径的长度小于最短路径的长度，就用存放着当前路径的栈中的数据替代存放最短路径的栈中的数据。当所有路径都找到以后，此时存放最短路径的栈中的数据即可表示该迷宫的最短路径。

结果演示：
          

在前面的博客中，我们已经解决了简单迷宫的求解问题以及多出口（不带环）迷宫求最短路径的问题。求带环的多出口迷宫的最短路径，需要我们在之前解决问题的思想上做出调整和改进。
首先，我们先来定义一个带环的多出口迷宫：
                  
图中黄色标记为一个环，0表示墙，即无法落脚；1表示可以落脚；之后我们会用2来标记走过的路。
我们默认出口为四个边界上的点。若入口也为边界点，则出口与入口不能重合。
解题思路的改进：
（1）CanStay函数。在之前的代码中，我们判断当前点是否能落脚，实现判断当前点是否在边界外，若在边界外则不能落脚；若在边界内且当前点的值为1，则可以落脚。但在求带环的多出口迷宫的最短路径时，我们还需要判断cur_value是否大于pre_value+1，若满足则应该落脚，若不满足则不应该落脚。
（2）Mark函数。在之前的代码中，我们将走过的路径点的值全部改为2，表示这个点已经走过。但在求带环的多出口迷宫的最短路径的问题时，我们不能简单的将走过的路径的点全部标记为一个特定的值。
                          
如上图所示，根据我们定义的按顺时针方向探测相邻点，那么该迷宫找到的第一条路径应该如图中蓝色数字标示所示。当找到一条路径后，进行出栈回溯，继续寻找下一条路径。
                        
此时就又新找到了一条路径。然后进行出栈回溯，继续新一轮的探测：
                        
当按顺时针方向进行探测时，走到图中红色圈出来的点后，就会发现，此时周围相邻的四个点要么无法落脚，要么已经走过，所以进行出栈回溯操作，继续寻找下一条路径。
                        
当回溯到上一个点后，按照顺时针探测的规则，下一个要走的点即为图中圈出来的点，当走到下一个点时，就相当于又找到了一条路径。相同地，进行出栈回溯，寻找下一条路径。此时会回溯到入口点，然后进行新一轮的探测。
                        
当回到入口点下面这个点时，向下进行探测时，发现下一个点已经被标记过，而右边的点不能落脚，所以探测就结束了。然而图中我们圈出来的这条路径，却没有被找到！
这就说明，在求带环的多出口迷宫的最短路径上，我们不能单纯地将已经走过的点标记为同一个特定值，而是应该采用新的方法：我们规定，将能落脚的入口点标记为2，之后的每个点都为上一个点的值+1，这样我们就得到了第一条路径的标记图：
                        
然后出栈回溯，寻找第二条路径：
                        
此时就找到了第二条路径。出栈回溯，继续寻找下一条路径：                        
                        
当走到图中标记为10的位置时，探测发现周围四个相邻点的值。探测上边的点时，发现3>10+1这个条件不满足，所以不应该落脚；探测右边和左边的点值为0，不能落脚，所以回溯到标记点为9的位置，继续新一轮的探测，发现当前位置左边的点满足标记条件，则直接落脚，并且此时又找到了一条路径。
                        
然后进行出栈回溯，回到标记为3的位置，按照顺时针方向，向下探测，发现10>3+1,所以可以落脚，并且将值改为4，之后的步骤同理：
                        
当走到图中圈出来的点时，向上探测，发现值为0不能落脚；向左探测发现7>6+1不成立，所以不能落脚；向下探测发现9>6+1成立，所以往下走，并修改标记值：
                        
这是就又找到了一条新的路径。以此方法类推，便能找到所有的路径。
（3）就如求解多出口迷宫（不带环）问题一样，由于多出口迷宫存在着多条路径，所以我们需要定义两个栈，一个栈中存放着当前走过的路径的数据，另一个栈中存放着最短路径的数据。每找到一条路径，就将当前路径的长度与最短路径的长度作比较，若存放最短路径的栈为空栈，或者当前路径的长度小于最短路径的长度，就用存放着当前路径的栈中的数据替代存放最短路径的栈中的数据。当所有路径都找到以后，此时存放最短路径的栈中的数据即可表示该迷宫的最短路径。
maze.h：
#pragma once
#include <stdio.h> 
#include<stdlib.h>
#include<stddef.h>

#define MAX_ROW 6
#define MAX_COL 6

typedef struct Point{
    int row;
    int col;
}Point;
typedef Point SeqStackType;

typedef struct SeqStack{
    SeqStackType *data;
    size_t size;
    size_t capacity;
}SeqStack;
typedef struct Maze{
    int map[MAX_ROW][MAX_COL];
}Maze;
maze.c：
#include "maze.h"
 
int map[MAX_ROW][MAX_COL]={
    {0,1,0,0,0,0},
    {0,1,1,1,0,0},
    {0,1,0,1,1,1},
    {1,1,1,1,0,0},
    {0,0,1,0,0,0},
    {0,0,1,0,0,0}
};

void MazeInitShortPathWithCycle(Maze* maze){
    if(maze == NULL)
        return;
    size_t i = 0;
    for(;i < MAX_ROW;i++){
        size_t j = 0;
        for(;j < MAX_COL;j++){
            maze->map[i][j] = map[i][j];
        }
    }
    return;
}

void SeqStackDebugPrint(SeqStack* stack,const char* msg){
    printf("%s\n",msg);
    if(stack == NULL)
        return;
    size_t i = 0;
    for(;i < stack->size;i++){
        printf("(%d,%d)\n",stack->data[i].row,stack->data[i].col);
    }
        printf("\n");
        return;
}

void MazePrint(Maze* maze){
    if(maze == NULL)
        return;
    size_t i = 0;
    for(;i < MAX_ROW;i++){
        size_t j = 0;
        for(;j < MAX_COL;j++)
            printf("%2d ",maze->map[i][j]);
        printf("\n");
    }
    return;
}
    
int CanStayWithCycle(Maze* maze,Point cur,Point pre){
    if(maze == 0)
        return 0;
    //判断当前点是否在地图上
    if(cur.row < 0 || cur.row >= MAX_ROW || cur.col < 0 || cur.col >= MAX_COL){
        return 0;
    }
    //判断是否为墙
    int cur_value = maze->map[cur.row][cur.col];
    int pre_value = maze->map[pre.row][pre.col];
    if(cur_value == 0){
        return 0;
    }
    //若当前点是1，可直接落脚
    if(cur_value == 1)
    return 1;
    //若当前点已走过，比较cur_value和pre_value的大小关系
    //若cur_value > pre_value+1,则应该落脚；否则不应该落脚
    if(cur_value > pre_value+1)
        return 1;
    return 0;
}

void MarkWithCycle(Maze* maze,Point cur,Point pre){
    if(pre.row == -1 && pre.col == -1){
        //单独考虑非法点的情况
        maze->map[cur.row][cur.col] = 2;
        return;
    }
    int pre_value = maze->map[pre.row][pre.col];
    maze->map[cur.row][cur.col] = pre_value + 1;
}

int IsExit(Maze* maze,Point cur,Point entry){
    (void)maze;
    //1.判断当前点是不是入口，若为入口，则不是出口
    if(cur.row == entry.row && cur.col == entry.col){
        return 0;
    }
    //2.如果当前点在地图边界上，说明是出口
    if(cur.row == 0 || cur.row == MAX_ROW-1 || cur.col == 0 || cur.col == MAX_COL-1){
        return 1;
    }
    return 0;
}

void SeqStackAssgin(SeqStack* from,SeqStack* to){
    //释放to中的原有内存
    SeqStackDestroy(to);
    //根据from中的元素个数确定内存申请的大小，给to重新申请一个足够的内存
    to->size = from->size;
    to->capacity = from->capacity;
    to->data = (SeqStackType*)malloc(to->capacity * sizeof(SeqStackType));
    //再进行数据拷贝
    size_t i = 0;
    for(;i < from->size;i++){
        to->data[i] = from->data[i];
    }
}

void _GetShortPathWithCycle(Maze* maze,Point cur,Point pre,Point entry,SeqStack* cur_path,SeqStack* short_path){
    printf("cur:(%d,%d)\n",cur.row,cur.col);
    //1.判断当前点能否落脚
    if(!CanStayWithCycle(maze,cur,pre)){
        return;
    }
    //2.若能落脚，给当前位置做一个标记
    //同时将当前点插入到cur_path
    MarkWithCycle(maze,cur,pre);
    SeqStackPush(cur_path,cur);
    //3.若当前点为出口，说明找到了一条出口
    if(IsExit(maze,cur,entry)){
        printf("找到了一条路径\n");
        if(cur_path->size < short_path->size || short_path->size == 0){
            //将当前路径与short_path中的路径对比，若当前路径比short_path短或short_path本身为空栈，则用当前路径替换short_path
            SeqStackAssgin(cur_path,short_path);
            printf("找到了一条相对较短的路径\n");
        }
        //若当前路径没有比short_path短，就尝试找其他路径
        SeqStackPop(cur_path);
        return;
    }
    //4.若当前点不是出口，则按顺时针方向探测四个相邻的点，递归式调用函数自身，递归式更新cur节点
    //（每次递归时，cur都是下一次要走的点，这个点能否落脚，交给递归函数作判断）
    Point up = cur;
    up.row -= 1;
    _GetShortPathWithCycle(maze,up,cur,entry,cur_path,short_path);

    Point right = cur;
    right.col += 1;
    _GetShortPathWithCycle(maze,right,cur,entry,cur_path,short_path);

    Point down = cur;
    down.row += 1;
    _GetShortPathWithCycle(maze,down,cur,entry,cur_path,short_path);

    Point left = cur;
    left.col -= 1;
    _GetShortPathWithCycle(maze,left,cur,entry,cur_path,short_path);
    
    //若四个方向都递归的探测过了，则可进行出栈，同时回溯到上一个点
    SeqStackPop(cur_path);
    return;
}

void GetShortPathWithCycle(Maze* maze,Point entry){
    SeqStack cur_path;
    SeqStack short_path;
    SeqStackInit(&cur_path);
    SeqStackInit(&short_path);
    Point pre = {-1,-1};
    _GetShortPathWithCycle(maze,entry,pre,entry,&cur_path,&short_path);
    SeqStackDebugPrint(&short_path,"最短路径为");
    return;
}
test.c:
#include "maze.h"
#define PRINT_HEADER printf("\n============%s============\n",__FUNCTION__);

void Test(){
    PRINT_HEADER;
    Maze maze;
    SeqStack stack;
    MazeInitShortPathWithCycle(&maze);
    Point entry = {0,1};
    GetShortPathWithCycle(&maze,entry);
    MazePrint(&maze);
}
int main(){
    Test();
    return 0;
}
结果演示：
                    

假如有以下带环的多出口迷宫地图： 

 

这里的思路与之前迷宫求解多出口求最短路径相似，不同的是，这里需要多传一个参数pre，保存当前要落脚的点的上一次走到这个点的大小 

1.判定当前点是否能落脚 

2.如果能落脚，进行标记，同时将当前点插入到cur_path栈中,更新pre 

3.判断是否是出口 

  a)如果是出口，就比较cur_path与short_path的大小，如果cur_path小就代替short_path 

  b)如果不是出口，以当前点为准则，采用递归式顺时针继续探测四周 

4.如果四周都探测过了，进行回溯 

解释： 

这里的判断是否能落脚的规则变了： 

1.判断当前点是否在地图上，相当于合法判定 

2.判定当前点是否是墙 

3.如果当前点是1，则可以直接落脚 

4.如果当前点已经被标记过了，就比较当前点与pre的大小，当当前点大于pre+1时，就可以落脚，否则不能落脚（结合如下代码看）； 

这里的标记规则也变了： 

首先，入口点的pre规定为（-1,-1），当pre为（-1，-1）时，就标记入口点为2，此后标记规则为，当前落脚点为pre+1;

具体代码实现如下：

 void MazeInit3(Maze* maze){                                                                                 
     if(maze == NULL){
         return;
     }
     int map[MAX_ROW][MAX_COL] = {
         {0,1,0,0,0,0},
         {0,1,1,1,0,0},
         {0,1,0,1,1,1},
         {1,1,1,1,0,0},
         {0,0,1,0,0,0},
         {0,0,1,0,0,0},
     };
     size_t i = 0;
     for(;i<MAX_ROW;i++){
         size_t j = 0;
         for(;j<MAX_COL;j++){
             maze->map[i][j] = map[i][j];
         }
     }
     return;
 }

 int CanStayWithCycle(Maze* maze,Point cur,Point pre){
     if(maze == NULL){
         return 0;
     }
     //当前点是否在地图上
     if(cur.row < 0||cur.col > MAX_COL||cur.row < 0 || cur.row > MAX_ROW){
         return 0;
     }
     int cur_value = maze->map[cur.row][cur.col];
     //当前点是墙
     if(cur_value == 0){
         return 0;
     }
     //当前点是1，就可以以直接落脚
     if(cur_value == 1){
         return 1;
     }
     //当前点如果已经被标记，就比较当前点与pre的大小                                                         
     //a)cur_value 7,pre_value 5 能落脚
     //b)cur_value 6,pre_value 5 不能落脚
     //c)cur_value 5,pre_value 5 不能落脚
     //d)cur_value 4,pre_value 5 不能落脚
     //总结以上情况，当cur_value > pre_value+1时能落脚
     int pre_value = maze->map[pre.row][pre.col];
     if(cur_value > pre_value+1){
         return 1;
     }
     return 0;
 }

 void MarkWithCycle(Maze* maze,Point cur,Point pre){
     if(maze == NULL){
         return;
     }
     if(cur.row < 0 || cur.row >=MAX_ROW || cur.col < 0 || cur.col >= MAX_COL){
         return;
     }
     if(pre.row == -1 && pre.col == -1){
         maze->map[cur.row][cur.col] = 2;
         return;
     }
     int pre_value = maze->map[pre.row][pre.col];
     maze->map[cur.row][cur.col] = pre_value + 1;
     return;
 }

 void _GetShortPathWithCycle(Maze* maze,Point cur,Point pre,Point entry,SeqStack* cur_path,SeqStack* short_path){
     if(maze == NULL){
         return;
     }
     //判断当前点是否能落脚（判定规则变了）
     if(!CanStayWithCycle(maze,cur,pre)){
         return;
     }
     //如果能落脚，就将当前点标记并且插入到cur_path中,更新pre
     MarkWithCycle(maze,cur,pre);
     SeqStackPush(cur_path,cur);
     pre = cur;
     //判断是否是出口
     if(IsEixt(maze,cur,entry)){                                                                             
         //如果是出口，要拿cur_path与short_path进行比较，
         //把比较短的路径保存到short_path中
         if(cur_path->size < short_path->size || short_path->size == 0){
             printf("找到了一条比较短的路径\n");
             SeqStackAssgin(cur_path,short_path);
         }                                                                                                   
         //进行回溯，不管当前找到的这条路径是不是比较短的路径
         SeqStackPop(cur_path);
         return;
     }
     //如果不是出口，以当前为基准，顺时针探测四周
     Point up = cur;
     up.row -= 1;
     _GetShortPathWithCycle(maze,up,pre,entry,cur_path,short_path);

     Point right = cur;
     right.col += 1;
     _GetShortPathWithCycle(maze,right,pre,entry,cur_path,short_path);

     Point down = cur;
     down.row += 1;
     _GetShortPathWithCycle(maze,down,pre,entry,cur_path,short_path);

     Point left = cur;
     left.col -= 1;
     _GetShortPathWithCycle(maze,left,pre,entry,cur_path,short_path);

     //如果四个点都探测过了，进行回溯
     SeqStackPop(cur_path);
     return;
 }

 void GetShortPathWithCycle(Maze* maze,Point entry){
     SeqStack cur_path;
     SeqStack short_path;
     SeqStackInit(&cur_path);
     SeqStackInit(&short_path);
     Point pre = {-1,-1};
        _GetShortPathWithCycle(maze,entry,pre,entry,&cur_path,&short_path);
     SeqStackDebugPrint(&short_path,"最短路径为");
 }

在迷宫求解2中，没有说到，当cur_path小于short_path时，进行替换，这里说一下: 

先将short_path中的元素释放掉，在根据cur_path的大小为short_path从新开辟空间，以保证肯定能够存放cur_path的元素，然后循环的将cur_path中的元素拷贝到short_path中即可； 

代码如下：



  void SeqStackAssgin(SeqStack* from,SeqStack* to){
      //为了保证to里面的内存能够足够的容纳from中的元素
      //就采用以下的策略：
      //1.释放to中的原有内存
      SeqStackDestroy(to);
      //2.根据from元素的个数，确定内存申请的大小
      //  给to重新申请一个足够的内存
      to->size = from->size;
      to->capacity = from->capacity;
      to->data = (SeqStackType*)malloc(to- >capacity*sizeof(SeqStackType));
      //3.再进行数据的拷贝                                                                                    
      size_t i = 0;
      for(;i<from->size;i++){
          to->data[i] = from->data[i];
      }
      return;
  }