1. 多通路迷宮初始化

????先構建一個多通路迷宮,并且對其初始化

void MazeInitShortPath(Maze* maze)
{if(maze == NULL){return;}int row = 0;int col = 0;for(; row < MAX_COL; row++){for(col = 0; col < MAX_COL; col++){maze -> map[row][col] = Map[row][col];}printf("\n");}
}

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

2. 定義一個棧并且打印

/** * @brief* * @用來測試迷宮棧* @param msg       */
void SeqStackDebugPrint(SeqStack* short_path, char* msg)
{printf("[%s]\n", msg);if(short_path == NULL || msg == NULL){return;}int i =0;for(;i < short_path -> size; i++){printf("(%d, %d)\n", short_path -> data[i].row, short_path -> data[i].col);}printf("\n");
}

3. 遞歸找通路

????在次過程中, 用到的思路和上一篇的迷宮求通路的思路一樣. 即就是利用遞歸的方式實現.不過因為此次有好多個出口, 所以我們每次都需要定義兩個棧, 保存當前路徑, 以及最短路徑, 最后將最短路徑中的內容打印出來.首先, 先判斷當前點是否可以落腳, 如果不能落腳, 就直接退出, 如果可以落腳, 就現將當前位置標記, 然后將其入棧, 再判斷當前位置是否是出口, 如果是出口就得判斷當前棧和最短路徑棧中它們兩個哪個路徑短, 如果當前路徑比最短路徑的步數少, 或者最短;路徑棧為空, 就用當前棧代替保存最短路徑的那個棧, 同時需要進行回溯, 將保存當前路徑的棧出棧.如果當前位置不是出口, 就對當前位置周圍的四個位置進行探索,直到找到出口為止. 如果當前位置周圍的四個點都已經探索, 此時就需要回溯了, 回溯的過程中也需要將保存當前位置的棧的元素出棧.

//輔助遞歸
void _GetShortPath(Maze* maze, Point cur, Point entry, SeqStack* cur_path, SeqStack* short_path)
{if(maze == NULL){return;}printf("(%d, %d)\n", cur.row, cur.col);//1. 判斷當前是否可以落腳if(CanStay(maze, cur) == 0){return;}//2. 能落腳就將其標記, 插入到cur_pathMark(maze, cur);SeqStackPush(cur_path, cur);//3. 判定當前是否是出口//b) 如果當前路徑沒有short_path短, 就回溯找其他路徑, 在回溯前也需要將 cur_path 出棧if(IsExit(maze, cur, entry)){printf("找到了一條較短的路\n");if(cur_path -> size < short_path -> size || short_path -> size == 0){//a) 如果是出口, 說明找到了一條路, 拿著當路徑和short_path 比較, 如果當前路徑比 short_path 路徑短, //應當前路徑代替 short_path(打擂臺), 或者 short_path 是個空棧, 就用當前棧代替short_path, 代替完//需要回溯, 找其他路徑SeqStackAssgin(short_path, cur_path);}SeqStackPop(cur_path);return;}//4. 當前點不是出口, 嘗試找四個方向(探測四個方向)Point up = cur;up.row -= 1;_GetShortPath(maze, up, entry, cur_path, short_path);Point right = cur;right.col += 1;_GetShortPath(maze, right, entry, cur_path, short_path);Point down = cur;down.row += 1;_GetShortPath(maze, down, entry, cur_path, short_path);Point left = cur;left.col -= 1;_GetShortPath(maze, left, entry, cur_path, short_path);//5. 如果四個方向都探測過了, 回溯返回到上一個點, 同時 cur_path 出棧 SeqStackPop(cur_path);
}
void GetShortPath(Maze* maze, Point entry)
{if(maze == NULL){return;}if(entry.row < 0 || entry.row >= MAX_ROW || entry.col < 0 || entry.col >= MAX_COL){return;}SeqStack cur_path;SeqStack short_path;SeqStackInit(&cur_path);SeqStackInit(&short_path);_GetShortPath(maze, entry, entry, &cur_path, &short_path);SeqStackDebugPrint(&short_path, "打印棧內容");printf("%d\n", short_path.size);
}

4. 棧的復制

????為了代碼實現的簡單, 我們定義兩個棧, from, to, from比to的元素要少. 在復制之前, 將to 的內存先進行釋放, 然后對to進行動態內存分配, 接著將 from 結構體的所有信息全部復制到 to 中,最后將from中的元素依次復制給 to即可

void SeqStackAssgin(SeqStack* to, SeqStack* from)
{if(from == NULL || to == NULL){return;}SeqStackDestroy(to);to -> data = (Point*)malloc(from -> capacity * sizeof(SeqStackType));to -> size = from -> size;int i = 0;for(; i < from -> size; i++){to -> data[i] = from -> data[i];}
}

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

5. 總結

????總結一下, 整體思路如下. 先定義兩個棧 cur_path , shrott_path, 前者保存當前路徑.后者保存最短路徑, 接著 判斷當前位置是否可以落腳, 如果不能落腳就直接返回, 如果可以落腳就將當前位置標記, 然后將當前點進行入棧, 入棧到 cur_path中, 接下來判斷當前位置是否為出口, 如果是出口, 就比較 cur_path 和 short_path 之間的長度, 如果 cur_path的元素少于 short_path 的元素或者 short_path 為空, 就用cur_path 代替 short_path, 然后將當前 cur_path 棧出棧, 接著進行回溯. 如果當前棧的元素個數大于 short_path棧的元素, 就將 cur_path 出棧, 然后進行回溯; 如果當前位置不是出口, 就按照順序(順時針)探測當前位置周圍的四個點, 如果當前位置周圍的四個點都已經探測, 此時說明進入了死胡同, 就需要回溯, 回溯之前不要忘記將當前的棧 cur_path 進行出棧, 最后,當遞歸結束時, 打印 short_path棧, 因為該棧里保存的就是最短路徑