本來(lái)之前寫(xiě)過(guò)一個(gè)推箱子，就想著寫(xiě)個(gè)迷宮游戲，因?yàn)橄胫葡渥佑螒蚶锩嬉灿袎?，也有玩家的移?dòng)，比推箱子簡(jiǎn)單的是還不用判斷前面是否有箱子的情況，但是自己寫(xiě)的迷宮游戲如果自己隨機(jī)生成的迷宮地圖的話，不一定會(huì)有通路，他要學(xué)一個(gè)什么隨機(jī)迷宮的生成，剛看完懶貓老師的那個(gè)迷宮問(wèn)題使用的是非遞歸DFS尋找迷宮是否有通路，用的是非遞歸DFS實(shí)現(xiàn)，然后隨機(jī)迷宮生成用的是DFS遞歸寫(xiě)的，我真的要成兩半了，今天分享給大家的是DFS算法找迷宮是否有出路，這個(gè)好像有的會(huì)作為數(shù)據(jù)結(jié)構(gòu)的大作業(yè)還是啥的，用c語(yǔ)言實(shí)現(xiàn)，參考b站懶貓老師的課迷宮問(wèn)題
1.問(wèn)題展示
2.棧的所有有用的函數(shù)
因?yàn)橐脳?shí)現(xiàn)，所以我們必須將有關(guān)棧的函數(shù)全部寫(xiě)出來(lái)，我們已經(jīng)之前寫(xiě)過(guò)棧的初始化，等等，棧的實(shí)現(xiàn)，我們將他拷貝過(guò)來(lái)，或者你們直接去看我那一篇。
//棧的實(shí)現(xiàn)
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef struct Stack//定義一個(gè)棧的結(jié)構(gòu)體變量
{
int * a;
int top; // 棧頂
int capacity; // 容量
}Stack;
void StackInit(Stack* ps)
{
assert(ps);//斷言，防止為空指針
ps->a = NULL;//所指向的地址為空
ps->capacity = ps->top = 0;//容量和棧中元素個(gè)數(shù)均為0
}
void StackPush(Stack* ps, int data)
{
assert(ps);
if (ps->capacity == ps->top)//如果棧中的元素個(gè)數(shù)等于棧的容量時(shí)考慮擴(kuò)容，
{
int newcapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;//如果剛開(kāi)始時(shí)都等于0，就先給4個(gè)空間大小，后面如果滿的話，容量擴(kuò)大1倍
int* newnode = (int*)realloc(ps->a,sizeof(int)* newcapcity);//申請(qǐng)空間，將申請(qǐng)好的空間首地址傳給newnode指針
assert(newnode);//斷言，防止malloc失敗
ps->a = newnode;//將newnode保存的申請(qǐng)空間的首地址傳給ps->a,讓ps->a指向創(chuàng)建好的空間
ps->capacity = newcapcity;//容量大小更新為新容量大小
}
ps->a[ps->top] = data;//像存數(shù)組一樣存數(shù)據(jù)
ps->top++;//指向下一個(gè)
}
// 檢測(cè)棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0
int StackEmpty(Stack* ps)
{
assert(ps);
return ps->top ==0;//ps->top為棧中元素個(gè)數(shù).==0棧中無(wú)元素，無(wú)元素要返回1， 無(wú)元素ps->t0p==0，這個(gè)表達(dá)式結(jié)果是1，返回1;
}
// 出棧
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));//防止棧內(nèi)無(wú)元素，繼續(xù)出棧
ps->top--;
}
// 獲取棧頂元素
int StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->a[ps->top - 1];//ps->top為棧中元素個(gè)數(shù)，由于數(shù)組下標(biāo)是從0開(kāi)始，所以棧頂元素下標(biāo)為ps->top-1;
}
// 獲取棧中有效元素個(gè)數(shù)
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
// 銷(xiāo)毀棧
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);//free掉動(dòng)態(tài)申請(qǐng)的內(nèi)存
ps->a = NULL;//防止野指針
ps->capacity = ps->top = 0;//容量和棧中元素個(gè)數(shù)置為0
}
但是不能直接用，所以我們必須加以修改，我們會(huì)將從入口到出口正確的路徑坐標(biāo)，以及每個(gè)坐標(biāo)對(duì)應(yīng)走向下一個(gè)坐標(biāo)的方向保存在棧里面，由我之前實(shí)現(xiàn)的棧中一個(gè)元素變?yōu)槿齻€(gè)元素，棧的實(shí)現(xiàn)做出以下改變，int * a，a指針不在指向一個(gè)int ，將inta改為proa;pro為結(jié)構(gòu)體類(lèi)型存放三個(gè)元素
typedef struct pro
{
int x;
int y;
int di;
}pro;
typedef struct Stack
{
pro* a;
int top; // 棧頂
int capacity; // 容量
}Stack;
由于一次壓進(jìn)三個(gè)數(shù)據(jù)，我們要修改入棧函數(shù)
void StackPush(Stack* ps, int data1, int data2, int data3)//入棧
{
assert(ps);
if (ps->capacity == ps->top)
{
int newcapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;
pro* tmp = (pro*)realloc(ps->a, sizeof(pro) * newcapcity);
if (tmp == NULL)
{
perror("realloc fail");
}
else
{
ps->a = tmp;
ps->capacity = newcapcity;
}
}
ps->a[ps->top].x = data1;
ps->a[ps->top].y = data2;
ps->a[ps->top].di = data3;
ps->top++;
}
由于每層由之前一個(gè)元素變?yōu)槿齻€(gè)元素，所以要修改獲取棧頂元素函數(shù)，返回棧頂?shù)刂?，然后通過(guò)地址來(lái)訪問(wèn)三個(gè)元素中的每一個(gè)
// 獲取棧頂元素
pro* StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->a+ps->top-1;
}
3.修改后的棧的實(shí)現(xiàn)
typedef struct pro
{
int x;
int y;
int di;
}pro;
typedef struct Stack
{
pro* a;
int top; // 棧頂
int capacity; // 容量
}Stack;
void StackInit(Stack* ps)//初始化棧
{
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
void StackPush(Stack* ps, int data1, int data2, int data3)//入棧
{
assert(ps);
//assert(ps->a);
if (ps->capacity == ps->top)
{
int newcapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;
pro* tmp = (pro*)realloc(ps->a, sizeof(pro) * newcapcity);
if (tmp == NULL)
{
perror("realloc fail");
}
else
{
ps->a = tmp;
ps->capacity = newcapcity;
}
}
ps->a[ps->top].x = data1;
ps->a[ps->top].y = data2;
ps->a[ps->top].di = data3;
ps->top++;
}
// 檢測(cè)棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0
int StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
// 出棧
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}
// 獲取棧頂元素
pro* StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->a+ps->top-1;
}
// 獲取棧中有效元素個(gè)數(shù)
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
// 銷(xiāo)毀棧
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
4. 定義二維數(shù)組作為迷宮的地圖
我們這里將1看做墻，0看做空地可以走的地方，然后迷宮入口坐標(biāo)為（1,1），我們定義二維數(shù)組為M*N的
#define N 10
#define M 10
迷宮出口坐標(biāo)為（M-2,N-2）;
定義全局變量，方便使用
int map[M][N] = {
{1,1,1,1,1,1,1,1,1,1},
{1,0,1,1,1,1,1,1,1,1},
{1,0,1,1,1,1,1,1,1,1},
{1,0,1,1,1,1,1,1,1,1},
{1,0,1,1,1,1,1,1,1,1},
{1,0,1,1,1,1,1,1,1,1},
{1,0,1,1,1,1,1,1,1,1},
{1,0,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1},
};
黑框標(biāo)注的分別為入口和出口.
在定義一個(gè)結(jié)構(gòu)體，表示要走的方向
typedef struct direct
{
int conx;
int cony;
}direct;
在主函數(shù)里面定義一個(gè)direct類(lèi)型的數(shù)組，數(shù)組大小為四，存放上下左右走，坐標(biāo)的變化，并且將他們賦值
direct des[4];
des[0].conx = 1;//向右走
des[0].cony = 0;
des[1].conx = -1;//向左走
des[1].cony = 0;
des[2].conx = 0;//向下走
des[2].cony = 1;
des[3].conx = 0;//向上走
des[3].cony = -1;
向哪走就給對(duì)應(yīng)坐標(biāo)+上什么的，比如說(shuō)我向右走，x+des[0].conx ,y+des[0].cony;
5.定義一個(gè)棧，將其初始化，當(dāng)用完時(shí)候?qū)⑵滗N(xiāo)毀
int main()
{
direct des[4];
des[0].conx = 1;//向右走
des[0].cony = 0;
des[1].conx = -1;//向左走
des[1].cony = 0;
des[2].conx = 0;//向下走
des[2].cony = 1;
des[3].conx = 0;//向上走
des[3].cony = -1;
Stack st;
StackInit(&st);
StackDestroy(&st);
StackDestroy(&scpy);
return 0;
}
6. DFS算法尋找迷宮是否有通路
bool findpath(int map[][N], direct des[], Stack* ps)
{
int line, col;//表示當(dāng)前位置能走的下一個(gè)位置的坐標(biāo)
int x, y, di;//表示當(dāng)前位置的坐標(biāo)，以及當(dāng)前位置準(zhǔn)備向下一個(gè)方向走的方向
int mapcon[M][N] = { 0 };//為了不修改原有的地圖，重新創(chuàng)建一個(gè)二維數(shù)組
for (int i = 0; i < M; i++)//遍歷地圖，將原地圖的二維數(shù)組的值拷貝到mapcon中
{
for (int j = 0; j < N; j++)
{
mapcon[i][j] = map[i][j];
}
}
mapcon[1][1] = -1;//走過(guò)的地方用-1標(biāo)記
pro tmp;//保存當(dāng)前位置的坐標(biāo)，以及方向
tmp.x = 1;
tmp.y = 1;
tmp.di = -1;//剛開(kāi)始在（1,1），將tmp.x，tmp.y賦值為1，剛開(kāi)始還沒(méi)有方向tmp.di = -1；
StackPush(ps, tmp.x, tmp.y, tmp.di);//將當(dāng)前位置信息壓入st棧中
while (!StackEmpty(ps))//棧中不為空，開(kāi)始循環(huán)
{
tmp.x = StackTop(ps)->x;
tmp.y = StackTop(ps)->y;
tmp.di = StackTop(ps)->di;//獲取棧頂元素到tmp中去，以便于回退
StackPop(ps);//出棧操作
x = tmp.x;//當(dāng)前坐標(biāo)改為回退之后的坐標(biāo)
y = tmp.y;//當(dāng)前坐標(biāo)改為回退之后的坐標(biāo)
di = tmp.di + 1;//開(kāi)始di=0,方向向右
while (di < 4)//遍歷當(dāng)前位置的四個(gè)方向
{
line = x + des[di].conx;//記錄下一個(gè)位置的坐標(biāo)
col = y + des[di].cony;//記錄下一個(gè)位置的坐標(biāo)
if (mapcon[line][col] == 0)//如果下一個(gè)坐標(biāo)時(shí)0，為空地的話，就可以前進(jìn)
{
tmp.x = x;//保存當(dāng)前位置坐標(biāo)，以便于回退
tmp.y = y;//保存當(dāng)前位置坐標(biāo)，以便于回退
tmp.di = di;//保存當(dāng)前位置坐標(biāo)，以便于回退
StackPush(ps, tmp.x, tmp.y, tmp.di);//當(dāng)前位置目前確定是通往出口路上的一個(gè)坐標(biāo)，先入棧
x = line;//當(dāng)前位置更新為下一個(gè)位置的坐標(biāo)
y = col;//當(dāng)前位置更新為下一個(gè)位置的坐標(biāo)
mapcon[line][col] = -1;//留下足跡，標(biāo)記為-1；
if (x == M - 2 && y == N - 2)//是否到出口
return true;//有通路，跳出
else di = 0;//沒(méi)到的話，將方向更新為向右
}
else di++;//如果當(dāng)前位置的方向不是空地的話，就換另一個(gè)方向判斷
}
}
return false;//循環(huán)結(jié)束，無(wú)通路
}
7. 逆序打印坐標(biāo)
如果有通路的話， findpath（）函數(shù)返回1，由于棧是先入后出，所以棧頂元素是出口的坐標(biāo)，怎么逆序打印從入口到出口的坐標(biāo)呢？我們可以在創(chuàng)建一個(gè)棧，使用棧判空函數(shù)循環(huán)將st中的元素入棧到另一個(gè)棧中，就做到了在原先棧底元素，跑到了新棧的棧頂，實(shí)現(xiàn)了逆序打印
Stack st;
Stack scpy;//定義一個(gè)棧用于倒翻數(shù)據(jù)
StackInit(&st);
StackInit(&scpy);//新棧初始話
bool ret = findpath(map, des, &st);//返回1，地圖有通路
if (ret == 1)
{
printf("該地圖有通路\n");
while (!StackEmpty(&st))//原棧不為空的話
{
int num1=StackTop(&st)->x;
int num2 = StackTop(&st)->y;
int num3= StackTop(&st)->di;//獲取舊棧棧頂元素
/*printf("%d-%d ",num1,num2);*/
StackPop(&st);//棧頂元素出st棧
StackPush(&scpy, num1, num2, num3);//棧頂元素入新棧scpy
}
while (!StackEmpty(&scpy))//新棧scpy不為空，
{
int num1 = StackTop(&scpy)->x;
int num2 = StackTop(&scpy)->y;
int num3 = StackTop(&scpy)->di;//獲取棧頂元素
printf("(%d,%d)\n", num1, num2);//打印棧頂元素
StackPop(&scpy);//新棧棧頂元素出棧
}
}
else
{
printf("該地圖無(wú)通路\n");
}
StackDestroy(&st);//銷(xiāo)毀舊棧
StackDestroy(&scpy);//銷(xiāo)毀新棧
只打印坐標(biāo)，不要求方向，我就在棧中沒(méi)畫(huà)方向.文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-714233.html
8.整體代碼
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
#define N 10
#define M 10
int map[M][N] = {
{1,1,1,1,1,1,1,1,1,1},
{1,0,1,1,1,1,1,1,1,1},
{1,0,1,1,1,1,1,1,1,1},
{1,0,1,1,1,1,1,1,1,1},
{1,0,1,1,1,1,1,1,1,1},
{1,0,1,1,1,1,1,1,1,1},
{1,0,1,1,1,1,1,1,1,1},
{1,0,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1},
};
typedef struct pro
{
int x;
int y;
int di;
}pro;
typedef struct direct
{
int conx;
int cony;
}direct;
typedef struct Stack
{
pro* a;
int top; // 棧頂
int capacity; // 容量
}Stack;
void StackInit(Stack* ps)//初始化棧
{
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
void StackPush(Stack* ps, int data1, int data2, int data3)//入棧
{
assert(ps);
//assert(ps->a);
if (ps->capacity == ps->top)
{
int newcapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;
pro* tmp = (pro*)realloc(ps->a, sizeof(pro) * newcapcity);
if (tmp == NULL)
{
perror("realloc fail");
}
else
{
ps->a = tmp;
ps->capacity = newcapcity;
}
}
ps->a[ps->top].x = data1;
ps->a[ps->top].y = data2;
ps->a[ps->top].di = data3;
ps->top++;
}
// 檢測(cè)棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0
int StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
// 出棧
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}
// 獲取棧頂元素
pro* StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->a+ps->top-1;
}
// 獲取棧中有效元素個(gè)數(shù)
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
// 銷(xiāo)毀棧
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
enum Mine
{
SPACE, //空地
WALL,//墻
DEST, //目的地
PLAYER//玩家
};
bool findpath(int map[][N], direct des[], Stack* ps)
{
int line, col;
int x, y, di;
int mapcon[M][N] = { 0 };
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
{
mapcon[i][j] = map[i][j];
}
}
mapcon[M - 2][N - 2] = 0;
mapcon[1][1] = -1;
pro tmp;
tmp.x = 1;
tmp.y = 1;
tmp.di = -1;
StackPush(ps, tmp.x, tmp.y, tmp.di);
while (!StackEmpty(ps))
{
tmp.x = StackTop(ps)->x;
tmp.y = StackTop(ps)->y;
tmp.di = StackTop(ps)->di;
StackPop(ps);
x = tmp.x;
y = tmp.y;
di = tmp.di + 1;
while (di < 4)
{
line = x + des[di].conx;
col = y + des[di].cony;
if (mapcon[line][col] == 0)
{
tmp.x = x;
tmp.y = y;
tmp.di = di;
StackPush(ps, tmp.x, tmp.y, tmp.di);
x = line;
y = col;
mapcon[line][col] = -1;
if (x == M - 2 && y == N - 2)
return true;
else di = 0;
}
else di++;
}
}
return false;
}
int main()
{
srand((unsigned int)time(NULL));
direct des[4];
des[0].conx = 1;//向右走
des[0].cony = 0;
des[1].conx = -1;//向左走
des[1].cony = 0;
des[2].conx = 0;//向下走
des[2].cony = 1;
des[3].conx = 0;//向上走
des[3].cony = -1;
Stack st;
Stack scpy;
StackInit(&st);
StackInit(&scpy);
bool ret = findpath(map, des, &st);
if (ret == 1)
{
printf("該地圖有通路\n");
while (!StackEmpty(&st))
{
int num1=StackTop(&st)->x;
int num2 = StackTop(&st)->y;
int num3= StackTop(&st)->di;
/*printf("%d-%d ",num1,num2);*/
StackPop(&st);
StackPush(&scpy, num1, num2, num3);
}
while (!StackEmpty(&scpy))
{
int num1 = StackTop(&scpy)->x;
int num2 = StackTop(&scpy)->y;
int num3 = StackTop(&scpy)->di;
printf("(%d,%d)\n", num1, num2);
StackPop(&scpy);
}
}
else
{
printf("該地圖無(wú)通路\n");
}
StackDestroy(&st);
StackDestroy(&scpy);
return 0;
}
9.編譯運(yùn)行
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-714233.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】迷宮問(wèn)題DFS非遞歸（c語(yǔ)言實(shí)現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![【Python數(shù)據(jù)結(jié)構(gòu)與算法】--- 遞歸算法的應(yīng)用 ---[烏龜走迷宮] |人工智能|探索掃地機(jī)器人工作原理](https://imgs.yssmx.com/Uploads/2024/02/752756-1.gif)
