首先來看一下迷宮簡易圖
????????????????????????????
????我們用 0 來表示該位置是墻, 用 1 來表示該位置是路. 所以, 我們在處理迷宮問題的時候可以將其看成一個二維數組即可, 而對應的每一條路我們可以用坐標的形式將其表示, 所以還需要有一個結構體來描述對應的點的
1. 相關數據結構

typedef struct Maze 
{int map[MAX_ROW][MAX_COL];
}Maze;
typedef struct Point
{int row;int col;
}Point;

2.迷宮初始化
????所謂的初始化迷宮就是將這個二維數組初始化, 我們自己定義一個二維數組, 然后將其每一個值賦值給我們的迷宮地圖即可

void MazeInit(Maze* maze)
{if(maze == NULL){return;}int Map[MAX_ROW][MAX_COL] = {{0, 1, 0, 0, 0, 0},{0, 1, 0, 0, 0, 0},{0, 1, 0, 0, 0, 0},{0, 1, 1, 1, 1, 0},{0, 0, 0, 1, 1, 0},{0, 0, 0, 1, 0, 0}};int row = 0;int col = 0;for(; row < MAX_ROW; row++){for(col = 0; col < MAX_COL; col++){maze -> map[row][col] = Map[row][col];}}
}

3.迷宮探索
????迷宮探索即就是從給出的迷宮入口開始, 一直往后探索, 直到找到出口為止. 我們利用函數在遞歸的過程中會形成棧楨的特性, 依次將我們所探索的為位置進行壓棧, 在此過程中, 我們必須得判斷當前的點是否合法, 同時必須判斷當前的點是否可以落腳, 如果可以落腳, 就現將該位置標記, 然后判斷當前位置是否是出口, 如果是出口, 說明迷宮探索完畢, 如果不是出口, 那么我們就得必須找下一個可以落腳的位置, 即我們依次按照順時針的方向依次遍歷當前位置四周的四個點(up, rught, down, left), 只要我們發現有一個點可以落腳, 我們就將當前位置對應的點入棧(調用函數本身), 當四個方向都已經走完了, 那么我們就得往回退, 即就是對應的出棧過程了.具體如下圖
????????????????????????????????????

void _GetPath(Maze* maze, Point cur, Point entry)
{if(maze == NULL){return;}if(cur.row < 0 || cur.row >= MAX_ROW || cur.col < 0 || cur.col > MAX_COL){return;}if(entry.row < 0 || entry.row >= MAX_ROW || entry.col < 0 || entry.col >= MAX_COL){return;}printf("(%d, %d)\n", cur.row, cur.col);//判斷當前點是否可以落腳if(CanStay(maze, cur))//如果可以落腳, 就給當前位置標記//如果當前點是出口, 則說明找到了一條路按順時針方向探測四個相鄰點, 遞歸調用函數自身, {Mark(maze, cur);if(IsExit(maze, cur, entry)){printf("找到了一條路\n");return;}//遞歸時更新 cur, (每次遞歸時, 這里的點是下次要走的點, 無論能不能走交給遞歸判斷)Point up = cur;up.row -= 1;_GetPath(maze, up, entry);Point right = cur;right.col += 1;_GetPath(maze, right, entry);Point down = cur;down.row += 1;_GetPath(maze, down, entry);Point left = cur;left.col -= 1;_GetPath(maze, left, entry);}else{return;}
}void GetPath(Maze* maze, Point entry)
{if(maze == NULL){return;//非法輸入}if(entry.row < 0 || entry.row >= MAX_ROW || entry.col < 0 || entry.col >= MAX_COL){return;}//輔助完成遞歸_GetPath(maze, entry, entry);MazePrint(maze);
}

4.判斷是否可以落腳
???? 即先判斷迷宮數據結構是否輸入合法, 接下來就是判斷當前位置是否合法, 如果不合法就退出, 如果當前位置對應的值是 1, 則說明能落腳, 否則就說明不能落腳.

int CanStay(Maze* maze, Point cur)
{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] == 1){return 1;}return 0;
}

5.判斷出口
????如果該位置到達迷宮邊界, 并且不等于入口位置, 則說明到達出口

int IsExit(Maze* maze, Point cur, Point entry)
{if(maze == NULL){return 0;}if(cur.row == entry.row && cur.col == entry.col){return 0;}if(cur.row == MAX_ROW -1 || cur.row == 0 || cur.col ==MAX_COL -1 || cur.col == 0){return 1;}return 0;
}

6.標記
????將當前位置的值賦值為2

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

7.打印迷宮函數

void MazePrint(Maze* maze)
{if(maze == NULL){return;//非法輸入}int row = 0;int col = 0;for(; row < MAX_ROW; row++){for(col = 0; col < MAX_COL; col++){printf("%2d ", maze -> map[row][col]);}printf("\n");}
}

????依次將回溯點打印出來,運行結果如圖
????????????????????????????????