廣度優先收索實作迷宮問題

定義一個二維數組：

int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,
           

};

它表示一個迷宮，其中的1表示牆壁，0表示可以走的路，隻能橫着走或豎着走，不能斜着走，要求程式設計式找出從左上角到右下角的最短路線。

Input

一個5 × 5的二維數組，表示一個迷宮。資料保證有唯一解。

Output

左上角到右下角的最短路徑，格式如樣例所示。

Sample Input

0 1 0 0 0

0 1 0 1 0

0 0 0 0 0

0 1 1 1 0

0 0 0 1 0

Sample Output

(0, 0)

(1, 0)

(2, 0)

(2, 1)

(2, 2)

(2, 3)

(2, 4)

(3, 4)

(4, 4)

分析：這個題使用廣度優先收索較為簡單，即找到最先到達左下方的路徑。

首先，從第一個元素開始周遊，遇到分支就建立一個結點，在繼續往後周遊，因為有可能兩個分支會周遊到同一個元素，是以每一個元素周遊後都應該給他做上标記。

其次，應該知道如何周遊。每次周遊到一個結點以後就讓這個結點進入隊列，然後再把隊首的結點拿出隊列進行比較，這個結點後面還有新的結點，就依次将新的結點入隊，隻到最後一個結點為止。

最後，輸出周遊後滿足條件的路徑。把最後一個結點到最後一個結點依次放進一個向量容器中，再從最後一個元素開始輸出，應為第一個元素時第一個結點，是以這個輸出是正向輸出而不是反向輸出。

源代碼：

#include<iostream>
#include<queue>
#include<sstream>
#include<vector>
#include<cstring>
using namespace std;

struct node
{
    int r,c;  // 記錄目前位置
    int pos;  // 記錄目前節點
    int pre;  // 記錄上一節點
    node(int r = ,int c = ,int pos = ,int pre = -):r(r),c(c),pos(pos),pre(pre){}
}t[];

const int dr[] = {-,,,};  //上下移動
const int dc[] = {,,,-};  //左右移動
int vis[][];   //标記已經被周遊過的元素
int mp[][];    //存放輸入的元素，即“圖”
int ptr;  //數組指針，記錄t中的元素個數

void print(node end)   //正向列印
{
    vector<node> cnt;
    cnt.push_back(end);  //将最後一個結點放進容器中
    for(int i = end.pre; i != -; i = t[i].pre)
    {
        cnt.push_back(t[i]);   //把最後一個到第一個元素依次放進容器中
    }
    for(int i = cnt.size()-;i >= ;i--)
    {
        cout<<"("<<cnt[i].r<<","<<cnt[i].c<<")"<<endl;   //從最後一個元素開始輸出，其實最後一個元素就是第一個元素
    }
}

void bfs()
{
    node st = node(,,,-);  //定義第一個結點
    queue<node> q;
    q.push(st);   //把第一個結點入棧
    t[ptr] = st;  //放入第一個結點
    memset(vis,,sizeof(vis));
    while(!q.empty())
    {
        node u = q.front();  //隊首元素出棧進行
        q.pop();
        if(u.r == && u.c == )
        {
            print(u);   //如果他是最後一個元素，就将他輸出
            return ;
        }
        for(int i = ;i < ;i++)
        {
            int newr = u.r + dr[i];  //往上下左右四個方向進行周遊
            int newc = u.c + dc[i];
            if(newr >= &&newr < &&newc >= &&newc < && mp[newr][newc] == && !vis[newr][newc])   
            {
                ptr++;
                node node_next = node(newr,newc,ptr,u.pos);  //定義新的結點
                vis[newr][newc] = ;  //标記周遊過的元素
                t[ptr] = node_next;   //把滿足條件的結點放入數組中
                q.push(node_next);    //元素進入隊列
            }
        }
    }
}

int main()
{
    for(int i = ;i < ;i++)   //輸入圖
    {
        for(int j = ;j < ;j++)
        {
            cin>>mp[i][j];
        }
    }
    bfs();   //周遊并輸出
    return ;
}