問題描述

參考上圖所示迷宮，編寫演演算法求一條從入口到出口的有效路徑。

途中陰影方塊代表牆（不可行走），白色方塊代表通道（支援行走）。
所求路徑必須是簡單路徑，即所求得的路徑上不能重複出現同一通道塊。

演演算法分析

初步分析

通常採用窮舉法，即從入口出發，順某一方向向前探索，若能走通，則繼續往前走；否則沿原路返回，換另一個方向繼續探索，直到探索到出口為止。為了保證在任何位置都能原路返回，顯然需要用一個先進後出的棧來儲存從入口到當前位置的路徑。

求迷宮中一條路徑的演演算法的基本思路是：

如果當前位置「可通」，則納入「當前路徑」，並繼續朝下一個位置探索，即切換下一個位置為當前位置，如此重複直至到達出口；如果當前位置不可通，則應沿「來向」退回到前一通道塊，然後朝「來向」之外的其他方向繼續探索；如果該通道塊的四周4個方塊均不可通，則應從當前路徑上刪除該通道塊。
所謂下一位置指的是當前位置四周（東、南、西、北）4個方向上相鄰的方塊。**

具體流程

1.宣告一個結構體patch表示每一個方塊，含有兩個成員：

（1）int type: 1-通道；0-牆；
（2）int flag: 1-未走；0-已走；-1-不可走。

2.建立一個矩陣表示迷宮，元素型別為結構體patch。

3.建立一個棧，用於儲存當前路徑依次所經過的每個patch的座標資訊（x, y）。

4.從當前位置cur出發（cur初始化為起點位置），然後基於cur按「東-南-西-北」4個方向順序依次試探，即按選定的試探方向往前進一個patch到達next位置：

（1）若next「可走」，則將cur入棧，同時將cur對應patch的flag更新為0，然後將cur更新為next，然後重複4；
（2）若next「不可走」，則改變試探方向基於cur前進一個patch獲取新next，然後重複（1）；
（3）若cur的「東-南-西-北」4個方向均「不可走」，則代表當前位置cur對應patch不可通，將cur對應patch的flag設為-1，執行出棧操作，並將cur更新為出棧元素對應的位置，將新cur對應patch的flag更新為1，然後重複4。
（4）若next等於終點，則將cur和next均入棧並將二者對應patch的flag更新為0，尋找有效路徑結束。
（5）尋找過程中，若當前位置cur重新回退至起點位置，代表所給迷宮無解。

5.棧記憶體儲的從「棧底元素 - 棧頂元素」對應的patch序列即為有效路徑。

程式碼實現

step1 : 結構體定義與建立

#include <iostream>
using namespace std;
#define MaxMazeSize 40   /* 迷宮的最大行列*/
#define MaxStackSize 100 /*棧的最大容量*/

/*宣告一個結構體表示patch的座標資訊*/
typedef struct
{
    int x, y;
} Position;

/* 宣告一個結構體patch表示每一個方塊 */
typedef struct
{
    int type = 0; // 0-牆；1-通道
    int flag = 1; // 0-已走；1-未走(可走)；-1-不可走(禁走)
} Patch;

/*宣告棧結構體*/
typedef struct
{
    Position data[MaxStackSize];
    Position *top = data; // 預設初始化棧
} PosStack;

PosStack S; // 建立棧儲存有效路徑座標資訊
Patch maze[MaxMazeSize][MaxMazeSize]; // 建立迷宮（二維列表）：元素型別為結構體patch
int rows, cols; // 迷宮的行數及列數
Position startPos, endPos; // 起點座標 + 終點座標

step2 : 迷宮初始化

/*初始化迷宮*/
void InitMaze()
{
    int walls;
    cout << "Please enter the number of rows and columns in the maze (separated by spaces):  ";
    cin >> rows >> cols;
    int k = 0;
    while (k < cols) // 設定迷宮外牆
    {
        maze[0][k].type = 0;
        maze[0][k].flag = -1;
        maze[rows - 1][k].type = 0;
        maze[rows - 1][k].flag = -1;
        k++;
    }
    k = 0;
    while (k < rows) // // 設定迷宮外牆
    {
        maze[k][0].type = 0;
        maze[k][0].flag = -1;
        maze[k][cols - 1].type = 0;
        maze[k][cols - 1].flag = -1;
        k++;
    }
    for (int i = 1; i < rows - 1; i++) // 內部區域全部初始化為通道
    {
        for (int j = 1; j < cols - 1; j++)
        {
            maze[i][j].type = 1;
            maze[i][j].flag = 1;
        }
    }
    cout << "Please enter the number of walls in the maze:  ";
    cin >> walls; // 使用者自定義設定內部區域牆的數量
    cout << "Enter the coordinates of each wall (x and y are separated by spaces):\n";
    int x, y;
    for (int i = 0; i < walls; i++) // 使用者自定義設定內部區域牆的位置
    {
        cin >> x >> y;
        maze[x][y].type = 0;
        maze[x][y].flag = -1;
    }
}

step3 : 展示迷宮

/*展示迷宮結構*/
void DisplayMaze(int rows, int cols)
{
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            cout << "\t" << maze[i][j].type;
        }
        cout << endl;
    }
}

step4 : 判斷某個位置對應的方塊是否可走

/*給定座標，判斷該座標對應patch是否可走*/
bool JudgeNext(Position next)
{
    if (next.x < 0 && next.y > rows - 1)
    { // 判斷該座標是否越界
        return false;
    }
    if (maze[next.y][next.x].type == 0)
    { // 判斷該座標對應patch是牆還是通道
        return false;
    }
    if (maze[next.y][next.x].flag <= 0)
    { // 判斷該座標對應patch是否可走
        return false;
    }
    return true;
}

step5 : 迷宮求解-尋找有效路徑

/*迷宮求解*/
bool FindMazePath()
{
    bool reFlag = false;
    Position curPos = startPos; // 當前位置
    Position nextPos;        // 下一試探位置
    int direction;
    while (1)
    {
        direction = 1;
        while (direction <= 4)
        {
            if (direction == 1) // 東
            {
                nextPos.x = curPos.x + 1;
                nextPos.y = curPos.y;
            }
            else if (direction == 2) // 南
            {
                nextPos.x = curPos.x;
                nextPos.y = curPos.y + 1;
            }
            else if (direction == 3) // 西
            {
                nextPos.x = curPos.x - 1;
                nextPos.y = curPos.y;
            }
            else // 北
            {
                nextPos.x = curPos.x;
                nextPos.y = curPos.y - 1;
            }
            if((nextPos.x == endPos.x) && (nextPos.y == endPos.y)){ // 抵達終點
                *(S.top++) = curPos;
                *(S.top++) = nextPos;
                maze[curPos.y][curPos.x].flag = 0;
                maze[nextPos.y][nextPos.x].flag = 0;
                reFlag = true;
                break;
            }
            if (JudgeNext(nextPos)){
                break;
            }else{
                direction++; // 準備嘗試下一試探方向
            }
        }
        if (direction > 4) // 當前位置不可通
        {
            maze[curPos.y][curPos.x].flag = -1;
            curPos = *(--S.top); // 執行出棧操作，並將當前位置更新為出棧patch對應位置
            maze[curPos.y][curPos.x].flag = 1;
        }else{  // next可走
            *(S.top++) = curPos;
            maze[curPos.y][curPos.x].flag = 0;
            curPos = nextPos;
        }
        if(reFlag){
            break; // 抵達終點，找到有效路徑，終止尋找
        }
        if((curPos.x == startPos.x) && (curPos.y == startPos.y)){
            cout << "Maze without a solution!\n";
            break;
        }
    }
    return reFlag;
}

step6 : 主方法呼叫

int main()
{
    InitMaze();
    cout << "The maze is structured as follows:\n";
    DisplayMaze(rows, cols);
    cout << "Please enter the coordinates of the starting point (x and y are separated by spaces):  ";
    cin >> startPos.x >> startPos.y;
    cout << "Please enter the coordinates of the end point (x and y are separated by spaces):  ";
    cin >> endPos.x >> endPos.y;
    if(FindMazePath()){
        cout << "Successfully found an effective path, as shown below:\n";
        int length = S.top - S.data;
        Position tmp;
        for(int i = 0; i< length; i++){
            tmp = *(--S.top);
            maze[tmp.y][tmp.x].type = length - i;
        }
        DisplayMaze(rows, cols);
    }else{
        cout << "Failed to find a effective path!\n";
    }
    system("pause");
    return 0;
}

執行效果

case1 : 迷宮有解

case2 : 迷宮無解

演演算法 | 迷宮求解