精华内容
下载资源
问答
  • 多出口迷宫最短路径求解

    千次阅读 2018-04-23 23:11:34
    有的时候,除了只有一条出口的迷宫外,我们还会遇到多出口迷宫求解问题,即 有条出口的迷宫,迷宫内部各路径不交叉,不成环,求其中最短的一条路径 例如: 关于单出口的简单迷宫求解,大家可以参考 ...

    问题引出

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

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

    例如:
    多出口迷宫
    关于单出口的简单迷宫求解,大家可以参考

    简单迷宫求解

    解题思路

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

    • 构建两个栈,一个栈为 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来标记走过...

    在前面的博客中,我们已经解决了简单迷宫的求解问题以及多出口(不带环)迷宫求最短路径的问题。求带环的多出口迷宫的最短路径,需要我们在之前解决问题的思想上做出调整和改进。

    • 首先,我们先来定义一个带环的多出口迷宫:

                      

    图中黄色标记为一个环,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.如果能落脚,...

    假如有以下带环的多出口迷宫地图:
    这里写图片描述
    这里的思路与之前迷宫求解多出口求最短路径相似,不同的是,这里需要多传一个参数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;
      }
    展开全文
  • 迷宫---多出口迷宫的最短路径

    千次阅读 2018-05-05 22:15:09
    如图是一个有三个出口迷宫,现在来求它的最短路径(不带环) 思想:定义两个栈,一个栈存放当前路径。一个栈存最短路径,每次都将当前路径和最短路径比较如果当前路径小于最短路径,那就交换两个栈中的元素 ...
  • 现在如果有出口,我们该如何去找到一条最短的路径。 我们先来思考一下我们是如何在一个数组里找最小值的? 有下面一个数组: 我们可以先把第一个数设为最小值,然后遍历数组,拿它和后面的元素进行比较,把...
  • /*求多出口迷宫的最短路径,非递归求法*/ Pos entry; entry._Row = 0; entry._COL = 1; int maze[5][5] = { { 0, 1, 0, 0, 0 }, { 0, 1, 1, 1, 0 }, { 0, 1, 0, 1, 1 }, { 1, 1, 0, 1, 0 }...
  • /*求多出口迷宫的最短路径,递归求法*/ /*迷宫地图*/ int Map[7][7] = { { 0, 1, 0, 0, 0, 0, 0 }, { 0, 1, 1, 1, 1, 1, 0 }, { 0, 1, 0, 0, 0, 1, 0 }, { 0, 1, 0, 0, 0, 1, 0 }, { 1, 1, 0...
  • void test3(){ TEST_HEADER; Maze maze; MazeInitShortPath(&maze); MazePrint(&maze); Point entry = { 0, 1 }; GetShortPath(&maze,entry); MazePrint(&maze); }
  • 多出口路径带环最短路径迷宫求解

    千次阅读 2018-04-23 23:18:38
    顾名思义,有出口迷宫迷宫内部各路径有交叉,成环,求其最短路径 例如: 解题思路 整体思路和多出口不带环迷宫最短路径求解一样,只是这次更改的是标记函数 Mark 与 判断是否能够落脚函数 Canstay ...
  • 寻找迷宫出口

    2008-08-07 12:37:12
    简单的用链栈实现找出一条迷宫出口
  • 迷宫

    2018-04-26 15:54:53
    迷宫的初始化一、 求简单迷宫是否存在路径 寻找路径的过程用递归来寻找路径Canstay函数:来实现是否可以落脚Mark函数:如果可以落脚则将其标记IsExit函数:二、多出口迷宫的最短路径(使用栈的思想)...
  • 迷宫出口以及迷宫最短路径的求解

    千次阅读 2017-04-20 15:36:57
    整理出来方便大家复习//完成迷宫 #pragma warning (disable:4996) #include #include #include using namespace std; #include //创建迷宫->动态创建二维数组:1.int[][N] 2.int*->(二维数组是按照一维数组来存储的...
  • 迷宫多出口

    千次阅读 2011-12-10 12:09:05
    /*  * =====================================================================================  *  * Filename: maze.c  *  * Description:  *  * Version: 1.0 ... * Created:
  • 迷宫中存在起点与终点,墙壁用数字2表示,行走路线用数字1表示,可行走的点用0表示。 #include <iostream> #include <map> #include <vector> #include <set> #include <iterator> ...
  • 利用广度优先探索算法,实现迷宫出口探索,数据结构
  • //stack.h #define _CRT_SECURE_NO_WARNINGS #pragma once #include <stddef.h> typedef struct point { int row; int col; }point; #define SEQ_STACK_SIZE 100 typedef struct SeqStack ...
  • MFC 深度搜索迷宫出口

    2010-07-12 22:28:45
    演示深度搜索找迷宫出口的过程。运用栈的知识,MFC的展示更为形象
  • 在一个指定的迷宫里,出口和入口指定,找到一条路出去
  • 迷宫求解问题

    2018-04-22 17:19:34
    迷宫求解问题:1. 简单迷宫是否存在路径(递归以及非递归实现) 2. 多出口迷宫的最短路径 3. 带环的多出口迷宫的最短路径
  • 假如有如下一个迷宫地图: 与迷宫求解1中,简单迷宫找路径思路相似,不同的是:这里需要定义两个栈cur_path和short_path,来存放当前路径长度,与最短路径长度,每找到一条路径就与最短路径进行比较,如果比最短...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,810
精华内容 3,924
关键字:

多出口迷宫