Maze迷宮問題（求最優解）

迷宮地形我們可以通過讀檔案的形式，通過已知入口逐個周遊坐标尋找通路。

檔案如圖：

每個坐标的位置用結構體來記錄：

struct Pos    //位置坐标
{
   int  _row;
   int _col;
};
      

　定義行列範圍：

#define M 10   //行
#define N 10   //列
      

初始化迷宮數組：

将通過讀檔案的方式擷取的字元轉成整型資料，儲存在M行N列的數組中。

void InitMaze(int* maze)
{  
    struct WavHeadhWAV;
    FILE* fout = fopen("MazeMap.txt", "r");   // .txt檔案要放在目前目錄下
    if (fout == NULL)                       // 這裡一定要檢查讀檔案是否成功
    {
        cout << "can't find MazeMap.txt !" << endl<<endl;
        return;
    }
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N;)
        {
            char ch = fgetc(fout);
            if (ch=='1'||ch=='0')
            {
                maze[i*N + j] = ch - '0';
                j++;
            }
        }
    }
    fclose(fout);
}
      

回溯查找通路：

利用棧來存儲通路，通過上下左右四個方向依次周遊，如果該位置滿足條件，就将它入棧，并将該位置的資料置為2；如果四個方向都不滿足條件就執行出棧操作，回溯查找滿足條件的位置（這時候如果棧為空了，說明查找通路失敗），繼續循環周遊，直到找到出口為止。

這裡建立一個最小棧，如果找到出路，就将該棧賦給最小棧，并将出口置為1，繼續回溯查找通路，如果又一次找到通路，就将該棧的長度與最小棧進行比較，如果該棧長度比最小棧還要小，就将它再一次賦給最小棧（保證最小棧是最短的通路），繼續回溯，直到整個棧為空，回到了入口，程式結束。

bool SearchMazePath(int *maze, Pos entry, stack<Pos>& paths)   // 利用棧回溯查找通路,并實作迷宮的最優解
{
    assert(maze);
    stack<Pos>min;
    paths.push(entry);
    while (!paths.empty())
    {
        Pos cur = paths.top();
        maze[cur._row*N+cur._col] = 2;
        if (cur._row==M-1)
        {
            if (paths.size()< min.size() || min.size() == 0)
            {
                min = paths;
            }
            paths.pop();
            maze[min.top()._row*N + min.top()._col] = 1;
        }  
        Pos next = cur;
        next._col--;  //左
        if (CheckIsAccess(maze, next))
        {
            paths.push(next);
            maze[next._row*N + next._col] = 2;
            continue;
        }
        next = cur;
        next._col++; //右
        if (CheckIsAccess(maze, next))
        {
            paths.push(next);
            maze[next._row*N + next._col] = 2;
            continue;
        }
        next = cur;
        next._row--; //上
        if (CheckIsAccess(maze, next))
        {
            paths.push(next);
            maze[next._row*N + next._col] = 2;
            continue;
        }
        next = cur;
        next._row++; //下
        if (CheckIsAccess(maze, next))
        {
            paths.push(next);
            maze[next._row*N + next._col] = 2;
            continue;
        }
        paths.pop();
    }
    if (paths.empty()&&!min.empty())
    {
            maze[min.top()._row*N + min.top()._col] = 2;
            return true;
    }
    return false;
}
      

　　檢查該位置是否合法：（坐标在行列範圍之内）

bool CheckIsAccess(int* maze, const Pos& next)    // 檢查該位置是否合法
{
    assert(maze);
    if ((next._row >= 0 && next._row <= N) && (next._col >= 0 && next._col < M) && maze[next._row*N + next._col] == 0)
    {
        return true;
    }
    return false;
}
      

　　列印迷宮：

void PrintMaze(int *maze)   // 列印迷宮
{
    assert(maze);
    for (int i = 0; i < M; i++)
    { 
        for (int j = 0; j < N; j++)
        {
            cout << maze[i*N + j] <<" " ;
        }
        cout << endl;
    }
    cout << endl;  
}