日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

 我們看下面這個迷宮----方陣（也可以是矩陣）：

10年積累的網(wǎng)站制作、成都網(wǎng)站建設(shè)經(jīng)驗，可以快速應(yīng)對客戶對網(wǎng)站的新想法和需求。提供各種問題對應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識你，你也不認(rèn)識我。但先做網(wǎng)站設(shè)計后付款的網(wǎng)站建設(shè)流程，更有西華免費網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

    迷宮入口是坐標(biāo)（2，0）位置，出口是（9，3）。我們假定0代表通路，1代表不通。

    現(xiàn)在需要找到哪一條路是通路。我們的思想是借助棧，“回溯法”。回溯是什么意思呢？？？先從起點出發(fā)，檢查它的上下左右是否是通路（即是否有為數(shù)字0處）。也就是說為0通了，壓棧，將此位置元素變成2，這樣做的好處是明確通路路徑。然后繼續(xù)往下走，判斷上下左右 。直至我們找到終點（縱坐標(biāo)在矩陣的最后一行）。

    我們來看下我針對迷宮問題實現(xiàn)的代碼：

---

#include
#include
#define N 10    //該迷宮10*10.

struct Pos    //定義一個結(jié)構(gòu)體，該結(jié)構(gòu)體用來表示坐標(biāo)。
{
    int _row;
    int _col;

    Pos(int row,int col)
        :_row(row)
        , _col(col)
    {}
};


template
bool SearchMazePath(int* a, int n, Pos entry, stack& paths)    //尋找迷宮是否有通路。
{
    assert(a);
    
    paths.push(entry);
    while (!paths.empty())
    {
        Pos cur = paths.top();
        a[cur._row*n + cur._col] = 2;            
        if (cur._row == n - 1)
        {
            return true;
        }

        //上
         Pos tmp = cur;
        --tmp._row;
        if (a[tmp._row*n + tmp._col] == 0)
        {
            paths.push(tmp);
            continue;
        }
        
        //下
        tmp = cur;    
        ++tmp._row;
        if (a[tmp._row*n + tmp._col] == 0)
        {
            paths.push(tmp);
            continue;
        }
        
        //左
        tmp = cur;        
        --tmp._col;
        if (a[tmp._row*n + tmp._col] == 0)
        {
            paths.push(tmp);
            continue;
        }
        
         //右
       tmp = cur;
        ++tmp._col;
        if (a[tmp._row*n + tmp._col] == 0)
        {
            paths.push(tmp);
            continue;
        }
        
        paths.pop();    //若上下左右都不通，則回溯。
    }
    
    return false;
}


void GetMaze(int* a, int n)    //讀取到迷宮圖案
{
    assert(a);
    FILE* fout = fopen("MazeMap.txt", "r");
    assert(fout);    //若文件打開失敗，后續(xù)工作則無法完成，因此采用assert防御式編程。
    
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            while (true)
            {
                int men = fgetc(fout);    //讀取字符
                if (men == '0' || men == '1')    //是0或者1則轉(zhuǎn)換成數(shù)字到二維矩陣中存儲。
                {
                    a[i*n + j] = men -'0';
                    break;    
                }                
            }
        }
    }       
}

void PrintMaze(int* a, int n)    //將此迷宮打印出來
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n;j++ )
        {
            cout << a[i*n + j] << "  ";
        }
        cout << endl;
    }
    cout << endl;
}


void Test()
{
    int a[N][N] = {};
    Pos sp(2, 0);    //入口坐標(biāo)
    
    GetMaze((int*) a, N);
    PrintMaze((int*)a, N);
    stack paths;
    
    SearchMazePath((int*)a, N, sp, paths);  
    //二維數(shù)組實際存儲是一維數(shù)組，將二維數(shù)組強(qiáng)制轉(zhuǎn)換為一維數(shù)組傳參。
    PrintMaze((int*)a, N);
}


int main()
{
    Test();
    system("pause");
    return 0;
}

     有時候，針對迷宮問題，我們還需要求多條路徑的最優(yōu)解（最短路徑）。那這時候我們可以用壓棧，利用棧幀一層一層壓棧的特點實現(xiàn)。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

分享名稱：【數(shù)據(jù)結(jié)構(gòu)】使用棧Stack解決迷宮問題-創(chuàng)新互聯(lián)
文章路徑：http://www.dlmjj.cn/article/edheh.html