前面介紹了簡(jiǎn)單的迷宮求解問(wèn)題, 今天我們就對(duì)帶環(huán)迷宮求出它的最短路徑

1.首先來(lái)看一個(gè)帶環(huán)迷宮的簡(jiǎn)單地圖

????????????????????????????????
????在這張迷宮地圖中,我們規(guī)定入口點(diǎn)的位置entry的坐標(biāo)是 (0, 1), 同時(shí), 我們給入口點(diǎn)傳一個(gè)非法坐標(biāo),作為入口點(diǎn)的前一個(gè)位置(-1, -1). 接下來(lái)的思路就和上一篇的思路是一樣的的了. 即每次判斷當(dāng)前點(diǎn)是否可以落腳, 如果不能落腳就直接退出, 如果可以落腳, 就將當(dāng)前位置的點(diǎn)進(jìn)行入棧操作, 將其標(biāo)記(和前面不一樣了), 接著判斷當(dāng)前點(diǎn)是否是出口, 如果是出口, 就將拿著 cur_path 和 short_path 進(jìn)行比較, 將較短的保存在 short_path 中, 然后將 cur_path 出棧, 接著再進(jìn)行回溯. 如果當(dāng)前點(diǎn)不是出口, 就按照順序依次探測(cè)當(dāng)前點(diǎn)周?chē)乃膫€(gè)點(diǎn), 如果四個(gè)點(diǎn)都已經(jīng)探測(cè)完了, 就需要回溯, 回溯的同時(shí)不要忘記將當(dāng)前棧 cur_path 出棧

2. 判斷當(dāng)前位置是否可以落腳

????判斷當(dāng)前位置是否可以落腳可以分為以下兩種情況
????(1)當(dāng)前位置還沒(méi)有走過(guò)
????此時(shí)地圖對(duì)應(yīng)的二維數(shù)組的值是 1, 即這個(gè)位置一定可以落腳
????(2)當(dāng)前位置如果已經(jīng)走過(guò), 我們需要借助當(dāng)前位置的前一個(gè)落腳元素來(lái)判斷當(dāng)前位置是否可以落腳, 當(dāng)前一個(gè)位置在地圖上對(duì)應(yīng)的值加1 小于當(dāng)前位置在地圖上的值的時(shí)候, 此時(shí)證明該位置就可以落腳, 即 cur > pre + 1此時(shí)就可以落腳

int CanStayWithCircle(Maze* maze, Point cur, Point prev) {if(maze == NULL){return 0;}if(cur.row < 0 || cur.row >= MAX_ROW || cur.col < 0 || cur.col >= MAX_COL){return 0;}//當(dāng)前位置是墻if(maze -> map[cur.row][cur.col] == 0){return 0;}//在取 prev 之前判斷 prev 是否合法if(prev.row == -1 && prev.col == -1){return 1;}//此時(shí)的prev 已經(jīng)不再是入口點(diǎn)的前一個(gè)坐標(biāo)if(prev.row < 0 || prev.row >= MAX_ROW || prev.col < 0 || prev.col >= MAX_COL){return 0;}//當(dāng)前位置已經(jīng)走過(guò), 比較 cur 和 prev 的大小關(guān)系if(maze -> map[cur.row][cur.col] > maze -> map[prev.row][prev.col] + 1){return 1;}//如果當(dāng)前點(diǎn)是 1 就直接可以落腳if(maze -> map[cur.row][cur.col] == 1){return 1;}return 0; }

3. 對(duì)當(dāng)前位置進(jìn)行標(biāo)記

????對(duì)當(dāng)前位置標(biāo)記分為兩種情況, 第一種就是看當(dāng)前位置是否為入口, 如果是入口, 就將地圖對(duì)應(yīng)的當(dāng)前位置處的坐標(biāo)變?yōu)?,否則就是讓 map[cur.row][cur.col] = map[prev.row][prev.col] + 1

void MarkShortPathWithCircle(Maze* maze, Point cur, Point prev) {if(maze == NULL){return;}if(cur.row < 0 || cur.row >= MAX_ROW || cur.col < 0 || cur.col >= MAX_COL){return;}if(prev.row < -1 || prev.row >= MAX_ROW || prev.col < -1 || prev.col >= MAX_COL){return;}if(prev.row == -1 && prev.col == -1){maze -> map[cur.row][cur.col] = 2;return;}maze -> map[cur.row][cur.col] = maze -> map[prev.row][prev.col] + 1;return; }

3. 迷宮求解遞歸代碼

int CanStayWithCircle(Maze* maze, Point cur, Point prev) {if(maze == NULL){return 0;}if(cur.row < 0 || cur.row >= MAX_ROW || cur.col < 0 || cur.col >= MAX_COL){return 0;}//當(dāng)前位置是墻if(maze -> map[cur.row][cur.col] == 0){return 0;}//在取 prev 之前判斷 prev 是否合法if(prev.row == -1 && prev.col == -1){return 1;}//此時(shí)的prev 已經(jīng)不再是入口點(diǎn)的前一個(gè)坐標(biāo)if(prev.row < 0 || prev.row >= MAX_ROW || prev.col < 0 || prev.col >= MAX_COL){return 0;}//當(dāng)前位置已經(jīng)走過(guò), 比較 cur 和 prev 的大小關(guān)系if(maze -> map[cur.row][cur.col] > maze -> map[prev.row][prev.col] + 1){return 1;}//如果當(dāng)前點(diǎn)是 1 就直接可以落腳if(maze -> map[cur.row][cur.col] == 1){return 1;}return 0; }void MarkShortPathWithCircle(Maze* maze, Point cur, Point prev) {if(maze == NULL){return;}if(cur.row < 0 || cur.row >= MAX_ROW || cur.col < 0 || cur.col >= MAX_COL){return;}if(prev.row < -1 || prev.row >= MAX_ROW || prev.col < -1 || prev.col >= MAX_COL){return;}if(prev.row == -1 && prev.col == -1){maze -> map[cur.row][cur.col] = 2;return;}maze -> map[cur.row][cur.col] = maze -> map[prev.row][prev.col] + 1;return; }void _GetShortPathWithCircle(Maze* maze, Point entry, Point cur, SeqStack* cur_path, SeqStack* short_path, Point prev) {if(maze == NULL){return;}if(entry.row < 0 || entry.row >= MAX_ROW || entry.col < 0 || entry.col >= MAX_COL){return;}if(cur.row < 0 || cur.row >= MAX_ROW || cur.col < 0 || cur.col >= MAX_COL){return;}if(cur_path == NULL || short_path == NULL){return;}//1. 判定當(dāng)前點(diǎn)是否可以落腳if(CanStayWithCircle(maze, cur, prev) == 0){return;}//2. 如果能落腳, 就標(biāo)記當(dāng)前點(diǎn), 并將其入棧到 cur_path中MarkShortPathWithCircle(maze, cur, prev);SeqStackPush(cur_path, cur);//3. 判定當(dāng)前是否是出口if(IsExit(maze, cur, entry))// a) 如果是出口, 就將 cur_path 和 short_path 比較, 把較短的路徑保存到 cur_path 中// 還有一種就是如果 short_path 的長(zhǎng)度為 0, 就用 cur_path 代替 short_path ,然后將 cur_path// 出棧, 并且回溯{printf("找到了一條路\n");if(cur_path -> size < short_path -> size || short_path -> size == 0){SeqStackAssgin(short_path, cur_path);}SeqStackPop(cur_path);return;}// b) 如果不是出口, 以當(dāng)前點(diǎn)為基準(zhǔn), 順時(shí)針探測(cè) 周?chē)膫€(gè)點(diǎn)Point up = cur;up.row -= 1;_GetShortPathWithCircle(maze, entry, up, cur_path, short_path, cur);Point right = cur;right.col += 1;_GetShortPathWithCircle(maze, entry, right, cur_path, short_path, cur);Point down = cur;down.row += 1;_GetShortPathWithCircle(maze, entry, down, cur_path, short_path, cur);Point left = cur;left.col -= 1;_GetShortPathWithCircle(maze, entry, left, cur_path, short_path, cur);//4. 如果四個(gè)方向都探測(cè)過(guò)了, 回溯SeqStackPop(cur_path);return; }void GetShortPathWithCircle(Maze* maze, Point entry, Point prev) {if(maze == NULL){return;//非法輸入}if(entry.row < 0 || entry.row >= MAX_ROW || entry.col < 0 || entry.col >= MAX_COL){return;//非法輸入}//規(guī)定第一個(gè)prev點(diǎn)的坐標(biāo)是(-1, -1)if(prev.row != -1 && prev.col != -1){return;}//定義兩個(gè)棧SeqStack cur_path;SeqStack short_path;//分別對(duì)這兩個(gè)棧進(jìn)行初始化SeqStackInit(&cur_path);SeqStackInit(&short_path);//輔助遞歸_GetShortPathWithCircle(maze, entry, entry, &cur_path, &short_path, prev);SeqStackDebugPrint(&short_path, "最短路徑"); }

????????????????????????????????

總結(jié)

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

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