前面介紹了簡單的迷宮求解問題, 今天我們就對帶環迷宮求出它的最短路徑

1.首先來看一個帶環迷宮的簡單地圖

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

2. 判斷當前位置是否可以落腳

????判斷當前位置是否可以落腳可以分為以下兩種情況
????(1)當前位置還沒有走過
????此時地圖對應的二維數組的值是 1, 即這個位置一定可以落腳
????(2)當前位置如果已經走過, 我們需要借助當前位置的前一個落腳元素來判斷當前位置是否可以落腳, 當前一個位置在地圖上對應的值加1 小于當前位置在地圖上的值的時候, 此時證明該位置就可以落腳, 即 cur > pre + 1此時就可以落腳

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;}//當前位置是墻if(maze -> map[cur.row][cur.col] == 0){return 0;}//在取 prev 之前判斷 prev 是否合法if(prev.row == -1 && prev.col == -1){return 1;}//此時的prev 已經不再是入口點的前一個坐標if(prev.row < 0 || prev.row >= MAX_ROW || prev.col < 0 || prev.col >= MAX_COL){return 0;}//當前位置已經走過, 比較 cur 和 prev 的大小關系if(maze -> map[cur.row][cur.col] > maze -> map[prev.row][prev.col] + 1){return 1;}//如果當前點是 1 就直接可以落腳if(maze -> map[cur.row][cur.col] == 1){return 1;}return 0;
}

3. 對當前位置進行標記

????對當前位置標記分為兩種情況, 第一種就是看當前位置是否為入口, 如果是入口, 就將地圖對應的當前位置處的坐標變為2,否則就是讓 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;}//當前位置是墻if(maze -> map[cur.row][cur.col] == 0){return 0;}//在取 prev 之前判斷 prev 是否合法if(prev.row == -1 && prev.col == -1){return 1;}//此時的prev 已經不再是入口點的前一個坐標if(prev.row < 0 || prev.row >= MAX_ROW || prev.col < 0 || prev.col >= MAX_COL){return 0;}//當前位置已經走過, 比較 cur 和 prev 的大小關系if(maze -> map[cur.row][cur.col] > maze -> map[prev.row][prev.col] + 1){return 1;}//如果當前點是 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. 判定當前點是否可以落腳if(CanStayWithCircle(maze, cur, prev) == 0){return;}//2. 如果能落腳, 就標記當前點, 并將其入棧到 cur_path中MarkShortPathWithCircle(maze, cur, prev);SeqStackPush(cur_path, cur);//3. 判定當前是否是出口if(IsExit(maze, cur, entry))// a) 如果是出口, 就將 cur_path 和 short_path 比較, 把較短的路徑保存到 cur_path 中// 還有一種就是如果 short_path 的長度為 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) 如果不是出口, 以當前點為基準, 順時針探測 周圍四個點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. 如果四個方向都探測過了, 回溯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;//非法輸入}//規定第一個prev點的坐標是(-1, -1)if(prev.row != -1 && prev.col != -1){return;}//定義兩個棧SeqStack cur_path;SeqStack short_path;//分別對這兩個棧進行初始化SeqStackInit(&cur_path);SeqStackInit(&short_path);//輔助遞歸_GetShortPathWithCircle(maze, entry, entry, &cur_path, &short_path, prev);SeqStackDebugPrint(&short_path, "最短路徑");
}

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