求解多出口迷宫的最短路径，是在基于求解简单迷宫是否存在路径的问题的基础上的一个提高。我们首先需要认识到的是，不论是求解简单迷宫问题，还是复杂迷宫的问题，我们都需要基于栈，使用回溯法来解决问题。

• 首先，我们先来定义一个多出口的迷宫：

图中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;
}

通过代码我们可以认识到，由于多出口迷宫存在着多条路径，所以我们需要定义两个栈，一个栈中存放着当前走过的路径的数据，另一个栈中存放着最短路径的数据。每找到一条路径，就将当前路径的长度与最短路径的长度作比较，若存放最短路径的栈为空栈，或者当前路径的长度小于最短路径的长度，就用存放着当前路径的栈中的数据替代存放最短路径的栈中的数据。当所有路径都找到以后，此时存放最短路径的栈中的数据即可表示该迷宫的最短路径。

结果演示：

如图是一个有三个出口的迷宫，现在来求它的最短路径（不带环）

思想：定义两个栈，一个栈存放当前路径。一个栈存最短路径，每次都将当前路径和最短路径比较如果当前路径小于最短路径，那就交换两个栈中的元素
代码实现：

void MazeInit2(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,0,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;
}
void _GetShortPath(Maze* maze,Point cur,Point entry,SeqStack* cur_path,SeqStack* short_path)
{
    //1.判断当前是否能落脚
    if(!CanStay(maze,cur))
    {
        return;
    }
    //2.如果能落脚，就对当前点进行标记，同时把当前点插入到cur_path
    Mark(maze,cur);
    SeqStackPush(cur_path,cur);
    //判断当前点是否是出口
    if(IsExit(maze,cur,entry))
    {
        //a）如果是出口，说明找到了一条路径，拿当前路径和short_path中的路径进行对比
        //，如果当前路径比short_path短，或short_path本身是一个空栈
        //  就用当前路径代替short_path
        printf("找到一条路经!\n");
        if(cur_path->size < short_path->size || short_path->size == 0)
        {
            printf("找到一条比较短的路径!\n");
            SeqStackAssgin(cur_path,short_path);
        //printf("cur :%d,%d\n",cur.row,cur.col);
        }
            //b)如果当前路径没有short_path短，就继续再找其他路径（进行回溯）
            //  回溯之前要把cur_path栈顶元素出栈
        SeqStackPop(cur_path);
        return;
    }
    //4.如果当前点不是出口，尝试探测四个方向（按照顺时针的方向探测）
    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);
    //5.如果四个方向都探测过了，就可以进行出栈（指当前函数栈帧结束
    //，同时cur_path,也要进行出栈），回溯到上一个点
    SeqStackPop(cur_path);
    return;
}
//找到所有路径，然后从所有的路径中筛选出一条最短的（递归）
void GetShortPath(Maze* maze,Point entry)
{
    //就像从一个数组中查找最小元素，一样，定义一个short_path保存最短路径
    SeqStack cur_path;//保存当前路径
    SeqStack short_path;//保存最短路径
    SeqStackInit(&cur_path);
    SeqStackInit(&short_path);
    _GetShortPath(maze,entry,entry,&cur_path,&short_path);
    SeqStackDebugPrint(&short_path,"最短路径");
}

seqstack.c中的代码实现

#ifdef FOR_MAZE
//#include<stdio.h>
//#include"seqstack.h"
//此函数仅用于迷宫问题，用来调试
//通常意义下，栈是不允许遍历的
//但是如果进行调试或者测试，就不一样了
//因此再这里虽然函数进行遍历了，但是仅用于调试
//之所以写这个函数遍历栈，是为了能够从入口到出口的顺序来打印栈的内容
void SeqStackDebugPrint(SeqStack* stack,const char* msg)
{
    printf("[%s]\n",msg);
    size_t i = 0;
    for(;i < stack->size ; ++i)
    {
        printf("(%d,%d)\n",stack->data[i].row,stack->data[i].col);
    }
    printf("\n");
}
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;
}
#endif

测试代码

void Test3()
{
    TEST_HEADER;
    Maze maze;
    MazeInit2(&maze);
    Point entry = {0,1};
    GetShortPath(&maze,entry);
    MazePrint(&maze);
}

运行结果：

如图是一个有三个出口的迷宫，现在来求它的最短路径（带环）

因为这个迷宫带环路径较多就不一一画出来了
第一次标记的结果

第二次标记的结果

第三次标记的结果

第四次标记结果

第五次标记结果

具体看代码实现

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.row >= MAX_ROW || cur.col < 0 || cur.col >= MAX_COL)
    {
        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_path 7,pre_value 5,应该落脚
    //b）cur_path 6,pre_value 5,不应该落脚
    //c）cur_path 5,pre_value 5,不应该落脚
    //d）cur_path 4,pre_value 5,不应该落脚
    //总结以上的几种情况可以总结出：cur_path > pre_path + 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 < 0 || pre.row >= MAX_ROW || pre.col < 0 || pre.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)
{
    //判定当前是否能落脚（判定规则变了）
    printf("cur :(%d,%d)\n",cur.row,cur.col);
    if(!CanStayWithCycle(maze,cur,pre))
    {
        return;
    }
    //标记当前点，并且将当前点插入到cur_path
    MarkWithCycle(maze,cur,pre);
    SeqStackPush(cur_path,cur);
    pre = cur;
    //判断当前点是否是出口
    if(IsExit(maze,cur,entry))
    {
        printf("找到了一条路径！\n");
        //如果是出口，要拿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,"最短路径为");
}

测试代码

void Test4()
{
    TEST_HEADER;
    Maze maze;
    MazeInit3(&maze);
    Point entry = {0,1};
    GetShortPathWithCycle(&maze,entry);
    MazePrint(&maze);
}

运行结果

前面我们实现了基础版本的迷宫求解，只有一条路径。现在如果有多个出口，我们该如何去找到一条最短的路径。

我们先来思考一下我们是如何在一个数组里找最小值的？
有下面一个数组：

我们可以先把第一个数设为最小值，然后遍历数组，拿它和后面的元素进行比较，把两个数中较小的赋给min,直到遍历完整个数组，min中就是数组中的最小值。

同样的，找最短路径也是一样的思路。我们可以定义两个栈，一个cur_path保存当前路径，一个short_path保存最短路径，每次找到一条路径，将它保存在cur_path里，并和short_path进行比较，将两条路径中较短的路径保存在short_path中，最后打印short_path的内容。

可以看出，黄色圈出来的就是最短路径。
步骤也是和前面大体一致，只是加了一个当前路径cur_path和最短路径short_path的比较,代码中有详解，大家可以参考一下.
话不多说，直接上代码:

//先对迷宫初始化
void MazeShortPathInit(Maze* maze)
{
    int map[MAX_ROW][MAX_COL] = {
        {0,1,0,0,0,0},
        {0,1,1,1,0,0},
        {0,1,0,1,0,0},
        {1,1,0,1,1,1},  
        {0,1,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;
}
//遍历所有的路径，然后从其中找出一条最短路径
//实现递归版本
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);
    //打印栈里面的内容（通常意义下，栈是不允许遍历的，但是这里仅仅用于调试）
    SeqStackPrintDebug(&short_path,"最短路径是：");
}

void _GetShortPath(Maze* maze,Point cur,Point entry,SeqStack* cur_path,SeqStack* short_path)
{
    //1.判断当前点是否能落脚
    if( !CanStay(maze,cur))
    {
        return;
    }
    //2.如果能落脚，标记当前点并且入栈到cur_path
    Mark(maze,cur);
    SeqStackPush(cur_path,cur);
    //3.判断当前点是否为出口
    if(IsExit(maze,cur,entry))
    {
    //  如果是出口，说明找到了一条路径，拿当前路径和short_path中的路径比较
    //  a)如果当前路径比short_path中路径短或者short_path为空，就用当前路径替换short_path
    //  b)如果当前路径没有short_path中路径短，尝试去找其他的路经（进行回溯），出栈cur_path的栈顶元素
        printf("找到了一条路径\n");
        if(cur_path->size < short_path->size || short_path->size == 0)
        {
            SeqStackAssgin(cur_path,short_path);
        }
        SeqStackPop(cur_path);
        return;
    }
    //4.如果当前点不是出口，尝试顺时针去探测其他四个方向
    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);
    //5.如果四个方向都递归的探测完了，就可以进行出栈(cur_path)，回溯到上一个点
    SeqStackPop(cur_path);
}

这里用到的辅助函数打印栈信息SeqStackPrintDebug（）和栈替换SeqStackAssgin（）如下，而判断当前点能不能落脚CanStay（）函数，判断是否是出口IsExit（）函数和标记Mark（）函数在之前博客中（基础版迷宫求解）写过，这里就不做具体介绍。

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

结果如下图：