精华内容
下载资源
问答
  • 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;
    }

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


    结果演示:

              

    展开全文
  • 迷宫---多出口迷宫的最短路径

    千次阅读 2018-05-05 22:15:09
    如图是一个有三个出口迷宫,现在来求它的最短路径(不带环) 思想:定义两个栈,一个栈存放当前路径。一个栈存最短路径,每次都将当前路径和最短路径比较如果当前路径小于最短路径,那就交换两个栈中的元素 ...

    如图是一个有三个出口的迷宫,现在来求它的最短路径(不带环)
    这里写图片描述
    思想:定义两个栈,一个栈存放当前路径。一个栈存最短路径,每次都将当前路径和最短路径比较如果当前路径小于最短路径,那就交换两个栈中的元素
    代码实现:

    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");
    }

    结果如下图:
    这里写图片描述

    展开全文
  • /*求多出口迷宫的最短路径,递归求法*/ /*迷宫地图*/ 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); }
  • 有一个N*M的格子迷宫,1代表该格子为墙,不能通过,0代表可以通过,另外,在迷宫中有一些传送门,走到传送门的入口即会自动被传送到传送门的出口(一次传送算1步)。人在迷宫中可以尝试上下左右四个方向移动。现在...
  • 如果存在出口,程序能够显示行走的路径,并最终到达出口,并输出“成功走出迷宫”;如果不存在出口,程序也能够显示行走的过程,并最终回退到入口,并输出“回退到入口”。 //这是一个迷宫游戏 #include #include #...
  • 迷宫问题

    2021-01-06 16:13:15
    //迷宫 int m,n;//m:出口层数 n:入口 int tag;//为输出做标记 int DFS(int k)//深度搜索第k层,k:当前路口 { int i,j; if(k==m)//到达出口 { tag=1; return 0; } for(i=0;i>n; if(0==n)break; int i,j; ...
  • 怪物追踪随机通路迷宫 g键添加怪物 迷宫wasd控制,找到迷宫出口为胜
  • 设计一个程序,对信任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。 【基本要求】 首先实现一个链表作存储结构的栈类型,然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的...
  • 用C++语言实现在迷宫中寻找出路。核心算法伪代码:do{如果当前位置为出口: 当前位置进栈;return 1;while(尝试的方向小于4){尝试方向号码对应方向的格子;如果这个格子是没走过的通路: 当前位置进栈; 将地图上...
  • 迷宫(课设).cpp

    2020-05-19 14:45:26
    盒子仅有一个出口,在出口处放置一块奶酪,吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验,一直到老鼠从入口到出口,而不走错一步。老鼠经次试验终于得到它学习走迷宫的路线。 通过本学期的...
  • 自己使用Java开发的进阶版迷宫,上下左右方向键控制主角移动,只显示主角周围一个圆区域,出口在最右下角;可以取消掉GameClient类里的注释显示辅助地图。
  • C语言走迷宫

    2019-02-26 09:14:26
    运行没有问题,能用 可以显示走的路径,自己输入50以下的二维路径就可以生成一个,然后使用栈算法,最终显示走出的路径标记 用井#号表示
  • 假如有如下一个迷宫地图: 与迷宫求解1中,简单迷宫找路径思路相似,不同的是:这里需要定义两个栈cur_path和short_path,来存放当前路径长度,与最短路径长度,每找到一条路径就与最短路径进行比较,如果比最短...
  • 给定一个m*n的迷宫,随机给出障碍物,使得小球从起点可以走到出口 2. 迷宫设计 这个视自己喜好设定,障碍物也随便设点,使用二维数组模拟迷宫,1即为墙壁与障碍物 3. 思路分析 使用递归来模拟小球运动,假设小球...
  • 迷宫算法

    2021-02-18 15:37:04
    迷宫算法 mouserecursion.py和mousestack.py作者:Aidan Good 该项目专注于创建解决任何迷宫的不同算法。 具有三个预定义的迷宫文件,或者用户可以请求随机生成的迷宫。 基于以下算法: 递归以查找所有可能的出口 ...
  • 如图所示,给出一个n*m的迷宫图和一个入口、一个出口 编写一个程序,打印从一条从迷宫入口到出口的路径。这里黑色方块的单元表示走不通(用-1表示),白色表示可以走(用0表示) 只能往上、下、左、右四个方向走。...
  • C++ 迷宫游戏实现代码

    2021-01-01 13:50:52
    题目 通过让游戏角色自动寻找迷宫出口,走出迷宫,来练习C++面向对象之封装的基础知识。迷宫图如下所示,其中X表示墙。   1、程序分析 走出去的原理:遵循右手规则或左手规则。右手扶墙走,就会走出迷宫,反之,...
  • 盒子仅有一个出口,在出口处放置一块奶酪,吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验,一直到老鼠从入口到出口,而不走错一步。老鼠经次试验终于得到它学习走通迷宫的路线。?????设计一...
  • 多出口路径带环最短路径迷宫求解

    千次阅读 2018-04-23 23:18:38
    顾名思义,有出口迷宫迷宫内部各路径有交叉,成环,求其最短路径 例如: 解题思路 整体思路和多出口不带环迷宫最短路径求解一样,只是这次更改的是标记函数 Mark 与 判断是否能够落脚函数 Canstay ...
  • 递归算法--01 迷宫问题:指定单入口和单出口,找到任意路径即可 问题背景: 给你一个 m x n 的迷宫矩阵 maze (下标从 0 开始),矩阵中有空格子(用 '.' 表示)和墙体(用 '+' 表示)。同时给你迷宫的入口 entrance...
  • 您必须通过按右键找到通往迷宫出口的路。 您必须按要移动的方格中的数字。 玩家只能上下左右移动。 如果卡住了,游戏就结束了。 游戏由五个不同的迷宫组成,这些迷宫是随机创建的。 每个级别的游戏都变得更难,第一...
  • 迷宫_迷宫_源码

    2021-10-04 02:06:22
    迷宫问题,根据给定入口出口,找出到达的所有路径

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,288
精华内容 4,515
关键字:

多出口迷宫