前端之家收集整理的这篇文章主要介绍了
【数据结构】用栈实现迷宫,
前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
#include <iostream>
using namespace std;
#define N 10
#include <stack>
struct pos
{
int _row;// 行
int _col;// 列
};
bool cheakstep(pos a)
{
if(a._col > -1||a._col < N-1||
a._row > -1||a._row < N-1)
{
return true ;
}
return false ;
}
bool IsPath(int arr[][N],pos nowloction,stack<pos>& s)
{
pos tmp = nowloction;
//入栈标记 栈不为空
s.push (nowloction);
arr[tmp._row][tmp._col] = 2;
while(!s.empty ())
{
//shang
pos now = s.top ();
if(now._row == N-1)
{
return true ;
}
now._row -=1;
if(cheakstep(now)==true && arr[now._row][now._col]==0)
{
s.push (now);
arr[now._row ][now._col ]=2;
continue;
}
//you
now = s.top ();
now._col +=1;
if(cheakstep(now)==true && arr[now._row][now._col]==0)
{
s.push (now);
arr[now._row ][now._col ]=2;
continue;
}
//xia
now = s.top ();
now._row +=1;
if(cheakstep(now)==true && arr[now._row][now._col]==0)
{
s.push (now);
arr[now._row ][now._col ]=2;
continue;
}
//zuo
now = s.top ();
now._col -=1;
if(cheakstep(now)==true && arr[now._row][now._col]==0)
{
s.push (now);
arr[now._row ][now._col ]=2;
continue;
}
else
{
now = s.top ();
arr[now._row ][now._col ] = 3;
s.pop ();
}
}
return false ;
}
int main()
{
//定义一个二维数组存放迷宫 1表示墙0表示路
//定义一个栈存放路径
//定义一个入口地址
int arr[N][N]={
1,1,};
pos entry = {2,0};
stack<pos> path;
bool ret = IsPath(arr,entry,path);
if(ret == true )
{
cout<< "走出迷宫"<<endl;
}
else
cout<< "没有走出迷宫"<<endl;
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
cout<<arr[i][j];
}
cout<<endl;
}
cout<<endl;
return 0;
}