作業內容三選一，感覺迷宮還行，可以做做，發現迷宮的恰當表示和隨機生成有學問啊
迷宮生成是將迷宮全部初始化為牆，然後打通牆，製造迷宮的過程
遞迴回溯演演算法
遞迴分割演演算法
隨機Prim演演算法
Kruskal演演算法
這篇部落格有動圖可以幫助理解 迷宮生成
這裡使用Prim演演算法
這裡的隨機使一般的最小生成樹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 )
一條路走到黑，走不動就返回，直到走到終點
DFS就不作過多陳述
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | |
+ +-+-+-+ + +-+ + +-+-+ + +-+ + +-+ +-+-+ + + +-+ + + + + +-+ +-+-+-+-+-+-+ + +
| | | | | | | | | | | | | | | | | | | | |
+-+ + + + +-+ + +-+-+ +-+-+-+-+-+ + + +-+-+ +-+ +-+ +-+ +-+-+-+ + + +-+-+-+ + +
| | | | | | | | | | | | | | | | | | | | | |
+ +-+ + +-+ + + + + +-+ + + + + +-+-+-+-+ +-+ + + +-+ +-+ +-+ +-+ + + +-+ +-+-+
| | | | | | | | | | | | | | | | | | | | | | |
+ +-+-+ +-+-+-+ +-+ + + +-+-+-+ +-+ + +-+-+ +-+-+ + + + +-+-+ + +-+ + + +-+ + +
| | | | | | | | | | | | | | | | | | | |
+-+-+-+-+-+-+ + + +-+-+ +-+-+-+-+ + + +-+-+-+ +-+-+ + +-+-+ +-+-+-+-+ +-+ + + +
| | | | | | | | | | | | | | | | |
+ +-+-+-+-+-+ +-+-+ +-+-+ + +-+-+ + + +-+-+ + + + + +-+-+ +-+-+-+-+ + + + +-+ +
| | | | | | | | | | | | | | | | | | | |
+-+-+ + +-+-+-+-+ +-+-+ +-+ + + +-+-+-+-+-+-+-+ +-+-+ + +-+-+ + + +-+ + +-+ + +
| | | | | | | | | | | | | | | | | | |
+-+ + + + + + + +-+-+ +-+ +-+ +-+-+ +-+-+ + +-+-+ + +-+-+-+ + + +-+-+-+ + +-+-+
| | | | | | | | | | | | | | | | | | | | |
+ +-+ + +-+-+-+ + + +-+ +-+ +-+-+ + +-+ + +-+-+-+ + +-+ +-+-+-+-+ +-+-+-+ +-+ +
| | | | | | | | | | | | | | | | | | | |
+-+-+-+ +-+ +-+-+ + +-+ + +-+ + +-+-+ + +-+-+ + +-+-+-+-+ + + + + + + +-+-+ + +
| | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
+.+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|. | | | | |....... | |...| | | |
+.+-+-+-+ + +-+ + +-+-+ + +-+ + +-+.+-+-+.+ + +-+ +.+.+ + +-+ +-+-+-+-+-+-+ + +
|...|...| | | | | | |...|.....| | | |.|...| | | | | |
+-+.+.+.+ +-+ + +-+-+ +-+-+-+-+-+.+ +.+-+-+ +-+ +-+.+-+.+-+-+-+ + + +-+-+-+ + +
|...|.|.| | | | | | |...| |.....| | |...|...| | | |.....| |
+.+-+.+.+-+ + + + + +-+ + + + +.+-+-+-+-+.+-+ + +.+-+.+-+ +-+ +-+ + +.+-+.+-+-+
|.....|.| | | | | | | |. |.....| | |.| |... | | | |.|...|...|
+ +-+-+.+-+-+-+ +-+ + + +-+-+-+.+-+ +.+-+-+ +-+-+.+ + +.+-+-+ + +-+ +.+.+-+.+.+
| |.......| | | |.........| | |. |.....| | |.....| | |.|...|.|.|
+-+-+-+-+-+-+.+ + +-+-+.+-+-+-+-+ + +.+-+-+-+.+-+-+ + +-+-+.+-+-+-+-+.+-+.+.+.+
| .| |.....|...| | |.......|.| | | |.........|.| |...|.|
+ +-+-+-+-+-+.+-+-+.+-+-+.+.+-+-+ + + +-+-+.+.+ + + +-+-+ +-+-+-+-+.+.+ + +-+.+
| | |.....|.......|.| | | |...| | | | | |...|.| | |.|
+-+-+ + +-+-+-+-+.+-+-+ +-+.+ + +-+-+-+-+-+-+-+ +-+-+ + +-+-+ + +.+-+.+ +-+ +.+
| | | | |.....| |...| | | | | | | | |.....| |.....|
+-+ + + + + + + +-+-+.+-+.+-+ +-+-+ +-+-+ + +-+-+ + +-+-+-+ + + +-+-+-+ +.+-+-+
| | | | | | | |...|...| | | | | | | | | |.| |
+ +-+ + +-+-+-+ + + +-+.+-+.+-+-+ + +-+ + +-+-+-+ + +-+ +-+-+-+-+ +-+-+-+.+-+ +
| | | | | |...|...| | | | | | | | | | |...| |
+-+-+-+ +-+ +-+-+ + +-+ +.+-+.+ +-+-+ + +-+-+ + +-+-+-+-+ + + + + + + +-+-+.+ +
| | | |..... | | | | | | |...|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+.+
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#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 <stdio.h>
#include <stdlib.h>
#include <time.h>
#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 */
本文來自部落格園，作者：江水為竭，轉載請註明原文連結：https://www.cnblogs.com/Az1r/p/16746269.html