迷宮的求解是一個(gè)經(jīng)典的問題，一直以來都想自己動手寫寫，雖然網(wǎng)上有無數(shù)的代碼，雖然對算法比較清楚，但我覺得只有在不參考任何資料的情況下，能寫的出來才算是真正掌握。今天有時(shí)間，有心情，終于靜下心來寫完了這個(gè)程序。盡管代碼很短，可還是花了兩個(gè)多小時(shí)，發(fā)現(xiàn)自己動手能力太差了。
????????下面是源碼：
#include?<iostream>
#include?<stack>
#include?<list>
#include?<assert.h>
#include?<fstream>

using?namespace?std;

struct?Position{??//定義位置結(jié)構(gòu)體
????int?r;
????int?c;
};

bool?FindPath(Position?start,Position?end,stack<Position>&?pos,int?**maze)
{
????Position?current?=?start;

????//定義探尋的四個(gè)方向
????Position?offset[4];
????offset[0].r=-1;?offset[0].c=0;???//up
????offset[1].r=0;??offset[1].c=1;???//right
????offset[2].r=1;??offset[2].c=0;???//down
????offset[3].r=0;??offset[3].c=-1;??//left

????int?di=0;
????int?lastDi=3;
????int?row,col;

????while(current.c!=end.c?||?current.r!=end.r)//沒有找到出口
????{
????????while(di<=lastDi)???//從當(dāng)前位置按順時(shí)針順序探尋
????????{
????????????row?=?current.r+offset[di].r;
????????????col?=?current.c+offset[di].c;
????????????if?(maze[row][col]?==?0)//下一個(gè)位置可行
????????????{
????????????????break;
????????????}
????????????di++;
????????}
????????//find?a?througth?path
????????if?(di?<=?lastDi)//找到下一個(gè)可行的位置
????????{
????????????pos.push(current);//將當(dāng)前位置入棧
????????????current.r?=?row;
????????????current.c?=?col;
????????????maze[row][col]?=?1;//標(biāo)記當(dāng)前位置為不可通過，以免陷入死循環(huán)
????????????di?=?0;
????????}
????????else//沒有找到相鄰的通行線路
????????{
????????????if?(pos.empty())//沒有找到通路
????????????{
????????????????return?false;
????????????}
????????????Position?next;
????????????next=?pos.top();
????????????pos.pop();
????????????if?(next.c?=?current.c)//取得當(dāng)前應(yīng)探尋的方向
????????????{
????????????????if?(?next.r>current.r?)
????????????????{
????????????????????di?=?1;
????????????????}
????????????????else
????????????????????di?=?3;
????????????}
????????????else?if?(next.r?=?current.r)
????????????{
????????????????di?=?3?+?next.c-current.c;
????????????}
????????????current?=?next;//標(biāo)記當(dāng)前位置為棧頂位置
????????}

????}
????pos.push(end);//將出口入棧

????return?true;
}

int?main()
{
????ifstream?in("maze.dat");//定義迷宮文件
????assert(in);????
????
????int?row,col;
????int?i,j;

????in>>row>>col;//讀入迷宮的行和列

????//定義迷宮數(shù)組，迷宮四周加墻，以使迷宮邊界與內(nèi)部節(jié)點(diǎn)同等處理
????int?**maze=new?int*[row+2];
????for?(i=0;?i<row+2;?i++)
????{
????????maze[i]?=new?int[col+2];
????}
????
????for?(i=0;i<row+2;i++)//迷宮四周為墻，設(shè)置為不可通過
????{
????????maze[i][0]?=?maze[i][col+1]?=?1;
????}
????for?(j=0;j<col+2;j++)
????{
????????maze[0][j]?=?maze[row+1][j]?=?1;
????}

????Position?start,end;
????in>>i>>j;???//讀入入口位置
????start.r=i;?start.c=j;
????in>>i>>j;???//讀入出口位置
????end.r=i;?end.c=j;

????//讀入迷宮數(shù)據(jù)
????for?(i=1;i<row+1;i++)
????{
????????for?(j=1;j<col+1;j++)
????????{
????????????in>>maze[i][j];
????????}
????}

????stack<Position>?path;
????list<Position>?show;
????if?(FindPath(start,end,path,maze))//找到一條路徑
????{
????????while?(!path.empty())
????????{
????????????show.push_front(path.top());//路徑出棧
????????????path.pop();
????????}

????????list<Position>::iterator?it=show.begin();
????????for?(;?it!=show.end();?it++)//顯示路徑
????????{
????????????cout<<"("<<(*it).r<<"?,?"<<(*it).c<<")"<<endl;
????????}
????}
????else//沒有找到路徑
????{
????????cout<<"Not?find?any?correct?path!"<<endl;
????}

????for?(i=0;?i<row+2;?i++)//釋放內(nèi)存空間
????{
????????delete?[]maze[i];
????}
????delete?[]maze;

????return?0;
}

????其中的文件結(jié)構(gòu)為：第一行，迷宮的行(ROW)和列(COL)
????????????????????????????第二行，迷宮的入口
????????????????????????????第三行，迷宮的出口
????????????????????????????第四行以后，迷宮數(shù)據(jù)，按行存儲，每行COL個(gè)0或1，共ROW行
????文件中數(shù)據(jù)以空格或回車或table隔開。不能含有其它字符。因?yàn)槲磳?shù)據(jù)進(jìn)行檢驗(yàn)，故無法識別數(shù)據(jù)結(jié)構(gòu)錯(cuò)誤。

????這是一個(gè)迷宮文件： maze.dat，因?yàn)樯蟼鞑恢С?dat，所以需要將.txt后綴改為.dat。

轉(zhuǎn)載于:https://www.cnblogs.com/chengy024/archive/2008/07/02/1234181.html

總結(jié)

以上是生活随笔為你收集整理的栈的应用——迷宫的非递归解法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。