栈是数据结构中一种重要的线性结构,限定仅在表尾进行插入和删除操作的线性表,因此我们也可以认为它是一种特殊的线性表。由于栈的这个特点,我们又可以称其为后进先出的结构。如图所示:
由于栈具有后进先出的性质我们可以利用,是程序设计中一个有用的工具。利用栈我们可以来实现数制转换、后缀表达式求值、迷宫求解等等。在书本上我们可以看到用C语言实现的简单思路,但是程序仍旧存在许多bug。今天,我想尝试用强大的C++来实现。
迷宫问题的求解思路大致则是从入口出发,顺着某一方向向前探索,若能走通,则继续向前探索;若不能走通,则换一方向进行探索,直至所有可能的通路都探索完为止。利用栈的特性,我们可以将探索过可通的路依次进栈,如果遇到不通的路则进行出栈操作,进行回退,重复探索。
ps:为了方便起见我利用了一个记事本来存放迷宫,用1表示不通,0表示通路。将走过的路程标注为2.
代码实现:
struct Pos //可通过下标访问位置
{
int _ROW;
int _COL;
};
void GetMaze(int *a,int n) //从文件中读出迷宫地图
{
FILE* fout=fopen("Maze.txt","r");
assert(fout);
for(int i=0; i<n; i++)
{
for(int j=0; j<n;
)
{
char ch=fgetc(fout);
if(ch=='0' || ch=='1')
{
a[i*n+j]=ch-'0';
++j;
}
else
{
continue;
}
}
}
fclose(fout);
}
bool CheckIsAccess(int *a,int n,Pos next)//检查是否为通路
{
assert(a);
if( (next._ROW>=0) && (next._ROW<n) && (next._COL>=0) && (next._COL<n) && (a[next._ROW*n+next._COL]==0))
{
return true;
}
else
{
return false;
}
}
bool MazePath(int *a,int n,Pos& entry,stack<Pos>& path) //探索过程
{
Pos cur=entry;
path.push(cur);
while(!path.empty())
{
Pos next=cur;
a[cur._ROW*n+cur._COL]=2;
if(next._ROW==n-1) /*|| next._ROW==0 || next._COL==n-1 || next._COL==0*/
{
return true;
}
//判断上下左右是否为通路
next=cur;
next._ROW--;// 上
if(CheckIsAccess(a,n,next))
{
cur=next;
path.push(cur);
continue;
}
next=cur;
next._ROW++;//下
if(CheckIsAccess(a,n,next))
{
cur=next;
path.push(cur);
continue;
}
next=cur;
next._COL--;//左
if(CheckIsAccess(a,n,next))
{
cur=next;
path.push(cur);
continue;
}
next=cur;
next._COL++;//右
if(CheckIsAccess(a,n,next))
{
cur=next;
path.push(cur);
continue;
}
//回退
cur=path.top();
path.pop();
}
}
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;
}
}
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。