迷宫问题详解

简介

  • 实验项目 2: 栈结构及其应用
  • 实验题目: 迷宫问题求解
  • 实验内容
    一个迷宫可以看成是由 m × n 个房间组成的矩形,迷宫内部的每个房间有 4个方向,每个方向或者有障碍(如墙)而不能通过,或者无障碍而能通过。 入口为左上角房间,出口为右下角房间,问是否有简单路径从入口到出口,若有则输出一条这样的路径;否则,提示迷宫无入口到出口路经
  • 实验要求
    1. 设计一个迷宫及其障碍的表示方式,并能随机或手动生成迷宫,并以适当方式展示。
    2. 设计并实现一个非递归的算法,输出从入口到出口的一条路径(如存在)。
    3. 设计并实现一个递归的算法,找出从入口到出口的一条路径(如存在)。
    4. 选做:如果有多条路径,设计并实现一个算法找到步数最少的路径(捷径)。
    5. 选做:如果有多条路径,设计并实现一个算法找到所有路径。
    6. 以适当的方式展示迷宫和所走路径

作业内容三选一,感觉迷宫还行,可以做做,发现迷宫的恰当表示和随机生成有学问啊

迷宫生成

迷宫生成是将迷宫全部初始化为墙,然后打通墙,制造迷宫的过程

基本知识
迷宫生成主要有四种方法

  • 递归回溯算法

    • 深度优先搜索,递归地打通未打通的区域
    • 思想简单,但生成的迷宫通路十分明显
  • 递归分割算法

    • 又名十字递归算法,递归地将地图分为四个房间,然后联通四个房间
    • 生成的迷宫就是像一个一个房间,适合RPG游戏
  • 随机Prim算法

    • 最小生成树算法,从已有的通路开始每次随机地选择一个方向打通迷宫
    • 通路不明显,适合迷宫游戏
  • Kruskal算法

    • 最小生成树算法,利用并查集随机地选择墙打通

这篇博客有动图可以帮助理解 迷宫生成

Prim算法

这里使用Prim算法

  1. 初始化迷宫全为墙。
  2. 选一个是迷宫通路的格子,然后随机选择它的邻墙。一般一开始的时候是起点(左上角)。
  3. 随机选择墙时:
  4. 如果它联通的格子不是迷宫的通路:
    1. 把墙打通。
    2. 自然那个格子变成了迷宫的通路.。
  5. 如果它联通的格子已经是通路了,选择其他格子去考虑邻墙。

这里的随机使一般的最小生成树Prim算法有所区别,该如何随机选择墙打通呢?

随机化种子

void srand(unsigned int seed) 播种由函数 rand 使用的随机数发生器。

int rand(void) 返回一个范围在 0 到 RAND_MAX 之间的伪随机数。

使用时间作为种子

srand(time(NULL));

srand ((int) time ((time_t *) NULL));

迷宫表示

设迷宫widthheight

表示迷宫一般是使用 \(width * height\) 大小的矩阵来表示,一个单元表示迷宫的通路与否。

如 11 * 4

.*****...**..**...*.*.*.*..*.*.*.*....***...

.表示通路

*或者#表示障碍

但是为了更好的表示迷宫,表示迷宫与通路的关系,方便我们观看

使用 + 单元 的方式来表示迷宫

则还需一圈外围围住迷宫的围墙

四方向

可以上下左右的走

总共需要 \((2*width + 1)*(2*height + 1)\) 大小的内存来表示

如 4 * 2

+-+-+-+-+| | | | |+-+-+-+-+| | | | |+-+-+-+-+

空格为一个迷宫单元,其他为墙

八方向

可以上下左右,且对角线的走

这样可以表示单元的上下左右与对角线的通路情况,虽然丑

很明显,一个九宫格,周围八个都是墙,中间是迷宫的单元

总共需要\((3 * height) * (3 * width)\) 大小的内存
如3 * 3

/=\/=\/=\| || || |\=/\=/\=//=\/=\/=\| || || |\=/\=/\=//=\/=\/=\| || || |\=/\=/\=/

迷宫解法

主要有三种解法

  • 深度优先搜索 DFS
  • 广度优先搜索 BFS
  • 启发式算法 A*

这里使用的深度优先搜索 ( DFS )

一条路走到黑,走不动就返回,直到走到终点

DFS就不作过多陈述

代码及运行结果迷宫数据类型定义

  • 采用结构体,中有6/10个变量
  • 4/8个方向,上下左右,(左上左下右上右下),表示该单元墙的打通情况
  • Visited变量,在DFS记录是否走过
  • Path变量,在DFS中记录是否为解法通路

四方向

+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+|         |     |       |     |   |         |     |   |     |               | |+ +-+-+-+ + +-+ + +-+-+ + +-+ + +-+ +-+-+ + + +-+ + + + + +-+ +-+-+-+-+-+-+ + +|   |   |   | |   |   |   |     |   |     | |   | | |   |     |   |       | | |+-+ + + + +-+ + +-+-+ +-+-+-+-+-+ + + +-+-+ +-+ +-+ +-+ +-+-+-+ + + +-+-+-+ + +|   | | |   | |   |   |   |   |   | |     | |   |   |   |     | |   |     |   |+ +-+ + +-+ + + + + +-+ + + + + +-+-+-+-+ +-+ + + +-+ +-+ +-+ +-+ + + +-+ +-+-+|     | |     | | |   | |   | |     |     |   | | | |     |   |   | | |   |   |+ +-+-+ +-+-+-+ +-+ + + +-+-+-+ +-+ + +-+-+ +-+-+ + + + +-+-+ + +-+ + + +-+ + +|     |       | |   | |         | | |       |     | | |     |   |   | |   | | |+-+-+-+-+-+-+ + + +-+-+ +-+-+-+-+ + + +-+-+-+ +-+-+ + +-+-+ +-+-+-+-+ +-+ + + +|             |   |     |   |     | |       | |   | |     |         | | |   | |+ +-+-+-+-+-+ +-+-+ +-+-+ + +-+-+ + + +-+-+ + + + + +-+-+ +-+-+-+-+ + + + +-+ +|     |     |     |       | |   |   |     |   | |   | |       | |   | |   | | |+-+-+ + +-+-+-+-+ +-+-+ +-+ + + +-+-+-+-+-+-+-+ +-+-+ + +-+-+ + + +-+ + +-+ + +|   | |     |   |     | |   | |           |     |   |   |   | | |     | |     |+-+ + + + + + + +-+-+ +-+ +-+ +-+-+ +-+-+ + +-+-+ + +-+-+-+ + + +-+-+-+ + +-+-+|   | | | |   | |   |   |   |     | |   | |       | |       |   |       | |   |+ +-+ + +-+-+-+ + + +-+ +-+ +-+-+ + +-+ + +-+-+-+ + +-+ +-+-+-+-+ +-+-+-+ +-+ +|     |     |   | |   |   |   |   |   | |     |   |     |     | | |     |   | |+-+-+-+ +-+ +-+-+ + +-+ + +-+ + +-+-+ + +-+-+ + +-+-+-+-+ + + + + + + +-+-+ + +|         |       |     |       |           |             | |   |   |     |   |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +

+.+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+|.        |     |       |     |   |.......  |     |...|     |               | |+.+-+-+-+ + +-+ + +-+-+ + +-+ + +-+.+-+-+.+ + +-+ +.+.+ + +-+ +-+-+-+-+-+-+ + +|...|...|   | |   |   |   |     |...|.....| |   | |.|...|     |   |       | | |+-+.+.+.+ +-+ + +-+-+ +-+-+-+-+-+.+ +.+-+-+ +-+ +-+.+-+.+-+-+-+ + + +-+-+-+ + +|...|.|.|   | |   |   |   |   |...| |.....| |   |...|...|     | |   |.....|   |+.+-+.+.+-+ + + + + +-+ + + + +.+-+-+-+-+.+-+ + +.+-+.+-+ +-+ +-+ + +.+-+.+-+-+|.....|.|     | | |   | |   | |.    |.....|   | |.| |...  |   |   | |.|...|...|+ +-+-+.+-+-+-+ +-+ + + +-+-+-+.+-+ +.+-+-+ +-+-+.+ + +.+-+-+ + +-+ +.+.+-+.+.+|     |.......| |   | |.........| | |.      |.....| | |.....|   |   |.|...|.|.|+-+-+-+-+-+-+.+ + +-+-+.+-+-+-+-+ + +.+-+-+-+.+-+-+ + +-+-+.+-+-+-+-+.+-+.+.+.+|            .|   |.....|...|     | |.......|.|   | |     |.........|.| |...|.|+ +-+-+-+-+-+.+-+-+.+-+-+.+.+-+-+ + + +-+-+.+.+ + + +-+-+ +-+-+-+-+.+.+ + +-+.+|     |     |.....|.......|.|   |   |     |...| |   | |       | |...|.|   | |.|+-+-+ + +-+-+-+-+.+-+-+ +-+.+ + +-+-+-+-+-+-+-+ +-+-+ + +-+-+ + +.+-+.+ +-+ +.+|   | |     |   |.....| |...| |           |     |   |   |   | | |.....| |.....|+-+ + + + + + + +-+-+.+-+.+-+ +-+-+ +-+-+ + +-+-+ + +-+-+-+ + + +-+-+-+ +.+-+-+|   | | | |   | |   |...|...|     | |   | |       | |       |   |       |.|   |+ +-+ + +-+-+-+ + + +-+.+-+.+-+-+ + +-+ + +-+-+-+ + +-+ +-+-+-+-+ +-+-+-+.+-+ +|     |     |   | |   |...|...|   |   | |     |   |     |     | | |     |...| |+-+-+-+ +-+ +-+-+ + +-+ +.+-+.+ +-+-+ + +-+-+ + +-+-+-+-+ + + + + + + +-+-+.+ +|         |       |     |.....  |           |             | |   |   |     |...|+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+.+

点击查看代码
#include #include #include #define WIDTH 39 #define HEIGHT 11#define UP 0#define RIGHT 1#define DOWN 2#define LEFT 3#ifdef TRUE#undef TRUE#endif /* TRUE */#define TRUE 1#define cell_empty(a) (!(a)->up && !(a)->right && !(a)->down && !(a)->left)typedef struct {    unsigned int up      : 1;//占一位     unsigned int right   : 1;    unsigned int down    : 1;    unsigned int left    : 1;    unsigned int path    : 1;    unsigned int visited : 1;}cell;typedef cell * maze_p;void CreateMaze (maze_p maze, int width, int height);void SolveMaze (maze_p maze, int width, int height);void PrintMaze (maze_p maze, int width, int height);int SolveMazeRec (maze_p maze, maze_p mp, int width, int height);int main (int argc, char *argv []){    int width = WIDTH;    int height = HEIGHT;    maze_p maze;    if (argc >= 2)        width = atoi (argv [1]);//atoi函数, 将一个字符串转化为整数     if (argc >= 3)        height = atoi (argv [2]);    if (argc >= 4)        srand (atoi (argv [3]));//随机种子     else        srand ((int) time ((time_t *) NULL));// 用系统时初始化随机种子     if (width <= 0 || height = maze && cell_empty (mp - width))            paths [directions ++] = UP;        if (mp < maze_pop && ((mp - maze + 1) % width) && cell_empty (mp + 1))//判断是不是最右             paths [directions ++] = RIGHT;        if ((mp + width)  maze && ((mp - maze) % width) && cell_empty (mp - 1)) //判断是不是最左             paths [directions ++] = LEFT;//在mp可选择的路中随机一个         if (directions) {            visits--;            directions = ((unsigned) rand () % directions);            switch (paths [directions]) {                case UP:                    mp->up = TRUE;//标记这个cell向上走                     (mp -= width)->down = TRUE;//相反,走过去的cell标记为向下走                     break;                case RIGHT:                    mp->right = TRUE;                    (++mp)->left = TRUE;                    break;                case DOWN:                    mp->down = TRUE;                    (mp += width)->up = TRUE;                    break;                case LEFT:                    mp->left = TRUE;                    (--mp)->right = TRUE;                    break;                default:                    break;            }        } else //没有可走的cell {            do {                if (++mp > maze_pop)//超过了就回到起点                     mp = maze;            } while (cell_empty (mp)); // 找到一个已被打通的cell         }    }}/* CreateMaze */int SolveMazeRec (maze_p maze, maze_p mp, int width, int height){mp->visited = TRUE;if(mp == (maze + (width * height) - 1)){mp->path = TRUE;return 0;}for(int sel = UP; sel up && !(mp - width)->visited){if( ! SolveMazeRec (maze, mp - width, width, height) ){mp->path = TRUE;return 0;}}break;case RIGHT:if (mp->right && !(mp + 1)->visited){if( ! SolveMazeRec (maze, mp + 1, width, height) ){mp->path = TRUE;return 0;}}break;case DOWN:if (mp->down && !(mp + width)->visited){if( ! SolveMazeRec (maze, mp + width, width, height) ){mp->path = TRUE;return 0;}}break;case LEFT:if (mp->left && !(mp - 1)->visited){if( ! SolveMazeRec (maze, mp - 1, width, height) ){mp->path = TRUE;return 0;}}break;default:break;}}return 1;}void SolveMaze (maze_p maze, int width, int height){    maze_p *stack, mp = maze;    int sp = 0;    stack = (maze_p *) calloc (width * height, sizeof (maze_p));    if (stack == NULL) {        (void) fprintf (stderr, "Cannot allocate memory!\n");        exit (EXIT_FAILURE);    }// 起点已访问      (stack [sp++] = mp)->visited = TRUE;    while (mp != (maze + (width * height) - 1)) //没到终点 {        if (mp->up && !(mp - width)->visited)//可走上,上没去过             stack [sp++] = mp - width;        if (mp->right && !(mp + 1)->visited)            stack [sp++] = mp + 1;        if (mp->down && !(mp + width)->visited)            stack [sp++] = mp + width;        if (mp->left && !(mp - 1)->visited)            stack [sp++] = mp - 1;        if (stack [sp - 1] == mp)            --sp;//如果走到头了,那就回去一步         (mp = stack [sp - 1])->visited = TRUE;//两步     }    while (sp--)//遍历一遍,标记为路径         if (stack [sp]->visited)            stack [sp]->path = TRUE;    free (stack);}/* SolveMaze */void PrintMaze (maze_p maze, int width, int height){    int w, h;    char *line, *lp;    line = (char *) calloc ((width + 1) * 2, sizeof (char));    if (line == NULL) {        (void) fprintf (stderr, "Cannot allocate memory!\n");        exit (EXIT_FAILURE);    }    maze->up = TRUE;    (maze + (width * height) - 1)->down = TRUE;    // 第一行     for (lp = line, w = 0; w up)//如果为出迷宫路径,则为 . ,否则为 空             *lp++ = ((maze + w)->path) ? '.' : ' ';        else            *lp++ = '-';    }    //一行 长 2*width + 1     *lp++ = '+';    (void) puts (line);        //system("pause");    for (h = 0; h < height; h++)// {        for (lp = line, w = 0; w left)                *lp++ = ((maze + w)->path && (maze + w - 1)->path) ? '.' : ' ';            else                *lp++ = '|';//墙             *lp++ = ((maze + w)->path) ? '.' : ' ';        }        *lp++ = '|';        (void) puts (line);        for (lp = line, w = 0; w down)                *lp++ = ((maze + w)->path && (h == height - 1 ||                         (maze + w + width)->path)) ? '.' : ' ';            else                *lp++ = '-';        }        *lp++ = '+';        (void) puts (line);        maze += width;    }    free (line);}/* PrintMaze */

八方向

/ \/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\|    ||    || || ||    || || || |\=/ =/\ /\= \=/\=/ =/\ /  /\=/\ //= /=\/ \/=\ =\/= /=\/  / \/=\/ \|    ||    ||    || || ||    || |\  \ /\=/\  \=/\=/\=/\=/\=/\ /\ // \  \/=\/ \ =\/=\/=\/=\/=\/ \/ \| || || || || || || ||    ||    |\= \=/  / =/\=/\  \=/ =/\=  = \=//=\ = /  /=\/=\/ \ = /=\/=  =\ =\| || || ||    || ||       || || |\=  = \=  =/\ /\  \= \=/\=/\= \ //=  =\ =  =\/ \/ \ =\ =\/=\/=\  \|    || || ||    || || || || || |\=/\=/\=/\=/\=/\=/\=/\=/\=/\=/\ /

/.\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\|....||....|| || ||....||.|| || |\=/.=/\./\=.\=/\=/.=/\./../\=/\ //=./=\/.\/=\.=\/=./=\/../.\/=\/ \|.   ||....||....|| ||.||....|| |\. \ /\=/\. \=/\=/\=/\=/\=/\./\ //.\  \/=\/.\ =\/=\/=\/=\/=\/.\/ \|.|| ||.||.|| || || ||....||.   |\=.\=/../.=/\=/\  \=/.=/\=..= \=//=\.=./../=\/=\/ \ =./=\/=..=\ =\| ||.||.||    || ||.......||.|| |\=  = \=  =/\ /\  \= \=/\=/\=.\ //=  =\ =  =\/ \/ \ =\ =\/=\/=\. \|    || || ||    || || || || ||.|\=/\=/\=/\=/\=/\=/\=/\=/\=/\=/\./

点击查看代码
/* * @Author: Az1r * @Date: 2022-09-30 20:47:13 */#include #include #include #define WIDTH 9#define HEIGHT 5#define UP 0#define RIGHT 1#define DOWN 2#define LEFT 3#define UL 4#define UR 5#define DL 6#define DR 7#ifdef TRUE#undef TRUE#endif /* TRUE */#define TRUE 1#define cell_empty(a) (!(a)->up && !(a)->right && !(a)->down && !(a)->left && !(a)->ul && !(a)->ur && !(a)->dl && !(a)->dr)typedef struct {    unsigned int up      : 1;//表示占1位    unsigned int right   : 1;    unsigned int down    : 1;    unsigned int left    : 1;        unsigned int ul      : 1;    unsigned int ur      : 1;    unsigned int dl      : 1;    unsigned int dr      : 1;    unsigned int path    : 1;    unsigned int visited : 1;}cell;typedef cell * maze_p;void CreateMaze (maze_p maze, int width, int height);void PrintMaze (maze_p maze, int width, int height); int SolveMazeRec (maze_p maze, maze_p mp, int width, int height);//递归版void SolveMaze (maze_p maze, int width, int height);//非递归版int main (int argc, char *argv []){    int width = WIDTH;    int height = HEIGHT;    int select = 0;    maze_p maze;    if (argc >= 2)        width = atoi (argv [1]);//atoi函数,字符串转整数    if (argc >= 3)        height = atoi (argv [2]);    if (argc >= 4)        srand (atoi (argv [3]));//随机种子     else        srand ((int) time ((time_t *) NULL));//以时间作为随机种子if(argc >= 5){select = atoi (argv [4]);}    if (width <= 0 || height = maze && cell_empty (mp - width))//若可以打通上面的墙,下同理            paths [directions ++] = UP;        if (mp < maze_pop && ((mp - maze + 1) % width) && cell_empty (mp + 1))            paths [directions ++] = RIGHT;        if ((mp + width)  maze && ((mp - maze) % width) && cell_empty (mp - 1))             paths [directions ++] = LEFT;        if ((mp - 1 - width) >= maze && ((mp - maze) % width) && mp > (maze + width - 1) && cell_empty (mp - 1 - width))        paths [directions ++] = UL;        if ((mp + 1 - width) > maze && ((mp - maze + 1) % width) && mp > (maze + width - 1) && cell_empty (mp + 1 - width))              paths [directions ++] = UR;        if ((mp - 1 + width) < maze_pop && ((mp - maze) % width) && mp <= (maze_pop - width) && cell_empty (mp - 1 + width))        paths [directions ++] = DL;        if ((mp + 1 + width) <= maze_pop && ((mp - maze + 1) % width) && mp up = TRUE;   //该单元上墙打通                    (mp -= width)->down = TRUE;//该单元上面的单元,下墙打通                    break;                     //以下同理                case RIGHT:                    mp->right = TRUE;                    (++mp)->left = TRUE;                    break;                case DOWN:                    mp->down = TRUE;                    (mp += width)->up = TRUE;                    break;                case LEFT:                    mp->left = TRUE;                    (--mp)->right = TRUE;                    break;                case UL:                mp->ul = TRUE;                (mp -= width + 1)->dr = TRUE;                break;                case UR:                mp->ur = TRUE;                (mp -= width - 1)->dl = TRUE;                break;                case DL:                mp->dl = TRUE;                (mp += width - 1)->ur = TRUE;                break;                case DR:                mp->dr = TRUE;                (mp += width + 1)->ul = TRUE;                break;                default:                    break;            }        } else //没有符合条件的墙{            do {                if (++mp > maze_pop)//超过了出口,就再从入口找起                    mp = maze;            } while (cell_empty (mp)); // 符合条件        }    }}/* CreateMaze */int SolveMazeRec (maze_p maze, maze_p mp, int width, int height){mp->visited = TRUE;if(mp == (maze + (width * height) - 1))//可以走到出口就是0{mp->path = TRUE;return 0;}for(int sel = UP; sel up && !(mp - width)->visited)//可以走上,下同{if( ! SolveMazeRec (maze, mp - width, width, height) ){mp->path = TRUE;return 0;}}break;case RIGHT:if (mp->right && !(mp + 1)->visited){if( ! SolveMazeRec (maze, mp + 1, width, height) ){mp->path = TRUE;return 0;}}break;case DOWN:if (mp->down && !(mp + width)->visited){if( ! SolveMazeRec (maze, mp + width, width, height) ){mp->path = TRUE;return 0;}}break;case LEFT:if (mp->left && !(mp - 1)->visited){if( ! SolveMazeRec (maze, mp - 1, width, height) ){mp->path = TRUE;return 0;}}break;case UL:if (mp->ul && !(mp - 1 - width)->visited){if( ! SolveMazeRec (maze, mp - 1 - width, width, height)){mp->path = TRUE;return 0;}}break;case UR:if (mp->ur && !(mp + 1 - width)->visited){if( ! SolveMazeRec (maze, mp + 1 - width, width, height)){mp->path = TRUE;return 0;}}break;case DL:if (mp->dl && !(mp - 1 + width)->visited){if (! SolveMazeRec (maze, mp - 1 + width, width, height)){mp->path = TRUE;return 0;}}break;case DR:if (mp->dr && !(mp + 1 + width)->visited){if (! SolveMazeRec (maze, mp + 1 + width, width, height)){mp->path = TRUE;return 0;}}break;default:break;}}return 1;}void SolveMaze (maze_p maze, int width, int height) {    maze_p *stack, mp = maze;    int sp = 0;    stack = (maze_p *) calloc (width * height, sizeof (maze_p));    if (stack == NULL) {        (void) fprintf (stderr, "Cannot allocate memory!\n");        exit (EXIT_FAILURE);    }//入口走过了    (stack [sp++] = mp)->visited = TRUE;    while (mp != (maze + (width * height) - 1)) //出口{        if (mp->up && !(mp - width)->visited)//判断是否可走,且是否走过;下面同理stack [sp++] = mp - width;        if (mp->right && !(mp + 1)->visited)            stack [sp++] = mp + 1;        if (mp->down && !(mp + width)->visited)            stack [sp++] = mp + width;        if (mp->left && !(mp - 1)->visited)            stack [sp++] = mp - 1;        if (mp->ul && !(mp - 1 - width)->visited)        stack [sp++] = mp - 1 - width;        if (mp->ur && !(mp + 1 - width)->visited)        stack [sp++] = mp + 1 -width;        if (mp->dl && !(mp - 1 + width)->visited)        stack [sp++] = mp - 1 + width;        if (mp->dr && !(mp + 1 + width)->visited)        stack [sp++] = mp + 1 + width;        if (stack [sp - 1] == mp)            --sp;//无路可走,那就回退        (mp = stack [sp - 1])->visited = TRUE;//这其实是两步    }    while (sp--)//回退栈,栈中保存的符合条件的即为路径        if (stack [sp]->visited)            stack [sp]->path = TRUE;    free (stack);}/* SolveMaze */void PrintMaze (maze_p maze, int width, int height){    int w, h;    char *line, *lp;    line = (char *) calloc ((width + 1) * 3, sizeof (char));    if (line == NULL) {        (void) fprintf (stderr, "Cannot allocate memory!\n");        exit (EXIT_FAILURE);    }    maze->up = TRUE;    (maze + (width * height) - 1)->down = TRUE;            //system("pause");    for (h = 0; h < height; h++){for (lp = line, w = 0; w ul)//若墙通,则要么走过,要么没走                *lp++ = ((maze + w)->path && (maze + w - 1 - width)->path) ? '.' : ' ';            else               //墙不通则打印墙            *lp++ = '/';                        if ((maze + w)->up)                *lp++ = ((maze + w)->path && ((maze + w - width)->path || h == 0) )? '.' : ' ';            else            *lp++ = '=';                        if ((maze + w)->ur)                *lp++ = ((maze + w)->path && (maze + w + 1 - width)->path) ? '.' : ' ';            else            {            *lp++ = '\\';}        }        (void) puts (line);        for (lp = line, w = 0; w left)                *lp++ = ((maze + w)->path && (maze + w - 1)->path) ? '.' : ' ';            else            *lp++ = '|';                        *lp++ = ((maze + w)->path) ? '.' : ' ';                        if ((maze + w)->right)                *lp++ = ((maze + w)->path && (maze + w + 1)->path) ? '.' : ' ';            else            *lp++ = '|';        }        (void) puts (line);                        for (lp = line, w = 0; w dl)                *lp++ = ((maze + w)->path && (maze + w - 1 + width)->path) ? '.' : ' ';            else            {            *lp++ = '\\';}                        if ((maze + w)->down)                *lp++ = ((maze + w)->path && ( (maze + w + width)->path || (h + 1) == height) ) ? '.' : ' ';            else            *lp++ = '=';                        if ((maze + w)->dr)                *lp++ = ((maze + w)->path && (maze + w + 1 + width)->path) ? '.' : ' ';            else            {            *lp++ = '/';}        }        (void) puts (line);                maze += width;    }    free (line);}/* PrintMaze */

参考博客

Random maze-generator FAQ

本文来自博客园,作者:江水为竭,转载请注明原文链接:https://www.cnblogs.com/Az1r/p/16746269.html

THE END
分享
二维码
< <上一篇
下一篇>>