文章目錄

• • 1 使用棧求解迷宮問(wèn)題

1 使用棧求解迷宮問(wèn)題

找迷宮通路需要使用回溯法，找迷宮通路是對(duì)回溯法的一個(gè)很好的應(yīng)用，實(shí)現(xiàn)回溯的過(guò)程用到數(shù)據(jù)結(jié)構(gòu)—棧！

回溯法： 對(duì)一個(gè)包括有很多個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)有若干個(gè)搜索分支的問(wèn)題，把原問(wèn)題分解為若干個(gè)子問(wèn)題求解的算法；當(dāng)搜索到某個(gè)結(jié)點(diǎn)發(fā)現(xiàn)無(wú)法再繼續(xù)搜索下去時(shí)，就讓搜索過(guò)程回溯(回退)到該節(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，繼續(xù)搜索該節(jié)點(diǎn)外的其他尚未搜索的分支；如果發(fā)現(xiàn)該結(jié)點(diǎn)無(wú)法再搜索下去，就讓搜索過(guò)程回溯到這個(gè)結(jié)點(diǎn)的前一結(jié)點(diǎn)繼續(xù)這樣的搜索過(guò)程；這樣的搜索過(guò)程一直進(jìn)行到搜索到問(wèn)題的解或者搜索完了全部可搜索分支沒(méi)有解存在為止。

地圖如下：

完整代碼如下：

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h>#define ROW 6 #define COL 6typedef struct _Maze {int map[ROW][COL]; }Maze;#define MAXSIZE 100typedef struct _Position {//迷宮坐標(biāo)int _x;int _y; }Position;#define MaxSize 128 //預(yù)先分配空間，這個(gè)數(shù)值根據(jù)實(shí)際需要預(yù)估確定typedef Position ElemType;typedef struct _SqStack {ElemType* base; //棧底指針ElemType* top; //棧頂指針 }SqStack;bool InitStack(SqStack& S) //構(gòu)造一個(gè)空棧 S {S.base = new ElemType[MaxSize];//為順序棧分配一個(gè)最大容量為 Maxsize的空間if (!S.base) //空間分配失敗return false;S.top = S.base; //top 初始為 base，空棧return true; }bool PushStack(SqStack& S, ElemType e) // 插入元素 e 為新的棧頂元素 {if (S.top - S.base == MaxSize) //棧滿return false;*(S.top++) = e; //元素 e 壓入棧頂，然后棧頂指針加 1，等價(jià)于*S.top=e;S.top++;return true; } bool PopStack(SqStack & S, ElemType & e) //刪除 S 的棧頂元素，暫存在變量 e中 {if (S.base == S.top) { //棧空return false;}e = *(--S.top); //棧頂指針減 1，將棧頂元素賦給 ereturn true; }ElemType* GetTop(SqStack & S) //返回 S 的棧頂元素，棧頂指針不變 {if (S.top != S.base) { //棧非空return S.top - 1; //返回棧頂元素的值，棧頂指針不變}else {return NULL;} }int GetSize(SqStack & S) {//返回棧中元素個(gè)數(shù)return (S.top - S.base); }bool IsEmpty(SqStack & S) {//判斷棧是否為空if (S.top == S.base) {return true;}else {return false;} }void DestoryStack(SqStack & S) {//銷毀棧if (S.base) {free(S.base);S.base = NULL;S.top = NULL;} }void InitMaze(Maze* m, int map[ROW][COL]) //迷宮的初始化 {for (int i = 0; i < ROW; ++i){for (int j = 0; j < COL; ++j){m->map[i][j] = map[i][j];}} }void PrintMaze(Maze* m) //打印迷宮 {for (int i = 0; i < ROW; ++i){for (int j = 0; j < COL; ++j){printf("%d ", m->map[i][j]);}printf("\n");}printf("\n"); }int IsValidEnter(Maze* m, Position cur) //判斷是否是有效的入口 {assert(m);if ((cur._x == 0 || cur._x == ROW - 1)|| (cur._y == 0 || cur._y == COL - 1)&& (m->map[cur._x][cur._y] == 1))return 1;elsereturn 0; }int IsNextPass(Maze* m, Position cur, Position next) //判斷當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)能否走通 {assert(m);//判斷 next 節(jié)點(diǎn)是否為 cur 的下一節(jié)點(diǎn)if (((next._x == cur._x) && ((next._y == cur._y + 1) || (next._y ==cur._y - 1))) //在同一行上并且相鄰|| ((next._y == cur._y) && ((next._x == cur._x + 1) || (next._x ==cur._x - 1)))) {//或在同一列上并且相鄰//判斷下一個(gè)節(jié)點(diǎn)是否在迷宮里面if (((next._x >= 0 && next._x < ROW) || (next._y >= 0 && next._y< COL))&& (m->map[next._x][next._y] == 1)) {return 1;}}return 0; }int IsValidExit(Maze* m, Position cur, Position enter) //判斷當(dāng)前節(jié)點(diǎn)是不是有效的迷宮出口 {assert(m);//這里首先得保證該節(jié)點(diǎn)不是入口點(diǎn)，其次只要它處在迷宮的邊界即可if ((cur._x != enter._x || cur._y != enter._y)&& ((cur._x == 0 || cur._x == ROW - 1)|| (cur._y == 0 || cur._y == COL - 1))){return 1;}elsereturn 0; }int PassMaze(Maze* m, Position enter, SqStack* s) //找迷宮通路 {assert(m && IsValidEnter(m, enter) == 1); //對(duì)給的迷宮的入口進(jìn)行合法性判斷Position cur = enter;Position next;PushStack(*s, cur); //首先將迷宮的入口壓入棧中m->map[cur._x][cur._y] = 2; //將入口值改為 2while (!IsEmpty(*s)) {cur = *GetTop(*s);//printf("cur: %d %d\n",cur._x, cur._y);if (IsValidExit(m, cur, enter) == 1) //判斷當(dāng)前位置是否出口return 1;//嘗試向左一步：看當(dāng)前節(jié)點(diǎn)的左一個(gè)節(jié)點(diǎn)能不能走通next = cur;next._y = cur._y - 1;if (IsNextPass(m, cur, next) == 1){PushStack(*s, next);m->map[next._x][next._y] = m->map[cur._x][cur._y] + 1;//PrintMaze(m);continue;}//嘗試向上一步:看當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)能不能走通next = cur;next._x = cur._x - 1;if (IsNextPass(m, cur, next) == 1) //next 節(jié)點(diǎn)能夠走通時(shí)，將其壓入棧中{PushStack(*s,next);m->map[next._x][next._y] = m->map[cur._x][cur._y] + 1; //將next 節(jié)點(diǎn)的值等于 cur 節(jié)點(diǎn)的值加 1//PrintMaze(m);continue;}//右：看當(dāng)前節(jié)點(diǎn)的向右的一個(gè)節(jié)點(diǎn)能不能走通next = cur;next._y = cur._y + 1;if (IsNextPass(m, cur, next) == 1){PushStack(*s, next);m->map[next._x][next._y] = m->map[cur._x][cur._y] + 1;//PrintMaze(m);continue;}//下：看當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)能不能走通next = cur;next._x = cur._x + 1;if (IsNextPass(m, cur, next) == 1){PushStack(*s, next);m->map[next._x][next._y] = m->map[cur._x][cur._y] + 1;//PrintMaze(m);continue;}//走到這里說(shuō)明當(dāng)前節(jié)點(diǎn)的四個(gè)方向都走不通，進(jìn)行回溯，看前一個(gè)節(jié)點(diǎn)未被遍歷的方向是否還能走通Position tmp;PopStack(*s, tmp);}return 0; }int main() {int map[ROW][COL] = { //用二維數(shù)組描繪迷宮：1 代表通路，0 代表墻0, 0, 1, 0, 0, 0,0, 0, 1, 1, 1, 0,0, 0, 1, 0, 0, 0,0, 1, 1, 1, 1, 0,0, 0, 1, 0, 1, 0,0, 0, 0, 0, 1, 0};Maze m;Position enter; //迷宮入口enter._x = 0;enter._y = 2;InitMaze(&m, map);PrintMaze(&m);//system("pause");//exit(0);SqStack s; //定義棧，保存已走過(guò)的坐標(biāo)軌跡，便于回溯InitStack(s); //棧的初始int ret = PassMaze(&m, enter, &s); //使用棧和回溯法解開(kāi)迷宮if (ret) {printf("恭喜你！終于找到了出口~\n");}else {printf("不是我笨！實(shí)在沒(méi)有出口~\n");}PrintMaze(&m);system("pause");return 0; }

---

參考資料：

C/C++從入門到精通-高級(jí)程序員之路【奇牛學(xué)院】

總結(jié)

以上是生活随笔為你收集整理的使用栈求解迷宫问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。