• 迷宫问题详解（数据结构实验）

    简介

    • 实验项目 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));

    迷宫表示

    设迷宫宽为width，高为height

    表示迷宫一般是使用 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 <= 0) 
	{
        (void) fprintf (stderr, "Illegal width or height value!\n");//错误输出流 
        exit (EXIT_FAILURE);
    }
    maze = (maze_p) calloc (width * height, sizeof (cell));//申请迷宫大小 
    if (maze == NULL) //申请失败 
	{
        (void) fprintf (stderr, "Cannot allocate memory!\n");//错误输出流 
        exit (EXIT_FAILURE);//宏定义的常量，是1；EXIT_SUCCESS 0  
    }
    CreateMaze (maze, width, height);//随机生成迷宫 

    PrintMaze (maze, width, height);//打印迷宫 

   	(void) puts("\n\nThe solve of maze:\n");
	
    //SolveMaze (maze, width, height);//解决迷宫 
	SolveMazeRec (maze, maze, width, height);
	
	
    PrintMaze (maze, width, height);//打印迷宫 
	
    free (maze);//释放 
    exit (EXIT_SUCCESS);

    return (0);

}/* main */


void CreateMaze (maze_p maze, int width, int height)
{
    maze_p mp, maze_pop;
    char paths [4];
    int visits, directions;

    visits = width * height - 1;//去掉 
    mp = maze;
    maze_pop = mp + (width * height) - 1;//右下角终点 

    while (visits) 
	{
        directions = 0;
			
		// 指针比大小，其实就是地址的比较 
        if ((mp - width) >= 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_pop && cell_empty (mp + width))
            paths [directions ++] = DOWN;
        if (mp > 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 <= LEFT; sel ++ )
	{
		switch(sel)
		{
			case UP:
				if (mp->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 < width; w++) 
	{
        *lp++ = '+';
        if ((maze + 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 < width; w++) 
		{
            if ((maze + 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 < width; w++) 
		{
            *lp++ = '+';
            if ((maze + 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 <= 0) 
	{
        (void) fprintf (stderr, "Illegal width or height value!\n");//error输出流
        exit (EXIT_FAILURE);
    }
    maze = (maze_p) calloc (width * height, sizeof (cell));
    if (maze == NULL) 
	{
        (void) fprintf (stderr, "Cannot allocate memory!\n");
        exit (EXIT_FAILURE);//内置的宏定义EXIT_SUCCESS 0 ，EXIT_FAILURE 1 
    }
    CreateMaze (maze, width, height);//随机生成迷宫

    PrintMaze (maze, width, height);//打印
	(void) puts("\n\n");
	if(select == 0)
	{
		SolveMaze (maze, width, height);
	}else
	{
		SolveMazeRec (maze, maze, width, height);
	}
   	/*
	随机生成迷宫的算法为prim算法，prim算法是最小生成树算法
    所以，每个迷宫单元都是连通的
    那么入口到出口一定存在一条通路
    若不算故意重复走的路径，那么这条通路是唯一的
    则，也是最短的
	*/
    PrintMaze (maze, width, height);
	
    free (maze);//释放
    exit (EXIT_SUCCESS);

    return (0);

}/* main */


void CreateMaze (maze_p maze, int width, int height)
{
    maze_p mp, maze_pop;
    char paths [8];
    
    int visits, directions;
    visits = width * height - 1;//除去入口
    mp = maze;
    maze_pop = mp + (width * height) - 1;// 出口

    while (visits) 
	{
        directions = 0;
			
		//找墙的过程
        if ((mp - width) >= 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_pop && cell_empty (mp + width))
            paths [directions ++] = DOWN;
        if (mp > 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 <= (maze_pop - width) && cell_empty (mp + 1 + width))
        	paths [directions ++] = DR;
        

		// 随机的过程
        if (directions) 
		{
            visits--;
            directions = ((unsigned) rand () % directions);

            switch (paths [directions]) 
			{
                case UP:
                    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 <= DR; sel ++ )
	{
		switch(sel)
		{
			case UP:
				if (mp->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 < width; w++) //上层
		{
            if ((maze + 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 < width; w++) //中层
		{
            if ((maze + 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 < width; w++) //单元的下层围墙
		{
            if ((maze + 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


    __EOF__

  • 本文作者： 江水为竭
  • 本文链接： https://www.cnblogs.com/Az1r/p/16746269.html
  • 关于博主： 评论和私信会在第一时间回复。或者直接私信我。
  • 版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
  • 声援博主： 如果您觉得文章对您有帮助，可以点击文章右下角【推荐】一下。
  • 相关阅读:
    Java设计模式之适配器模式(类结构型、对象结构型，双向适配器)
    QStringLiteral(str)
    Sitime SIT8009BI-82-33E-125.000000Y 125M晶振
    动态规划 Ⅱ
    dtcloud 的消息机制（二）
    游戏开发中，常见的贴图压缩方式
    数据库（一）
    抖店运营需要多少资金，最新入驻费用详解！
    30岁测试开发年薪不足80万，还要被面试官diss混得太差？
    《程序员数学：斐波那契》—— 为什么不能用斐波那契散列，做数据库路由算法？
  • 原文地址：https://www.cnblogs.com/Az1r/p/16746269.html