大家都知道，至于迷宫的求解问题，可以用穷举法进行求解。那么什么是穷举法了，就是将每一种可能的情况都穷举完。而具体到迷宫的求解问题上，由于在求解过程中可能会遇到某一路径不可行的情况，此时我们就必须按原路返回，这时自然也就会想到栈的应用了，因为栈的一个很重要的特性就是”先进后出”，可以用来记录每次所探索的路径，方便在原路返回的过程中，得到上一步所走路径，再按此方法，退回到可以走得通的位置上，继续探索下去，直到到达终点或者最终无法到达，正常退出程序为止。
下面我们就一起来探索迷宫！！！
首先是得到迷宫地图，这里我们用文件流来实现。
计算
安全
数据库
网络和加速
企业服务
void GetMaze(int *a, size_t n)
{
FILE* fout = fopen("MazeMap.txt", "r"); //打开迷宫地图
assert(fout);
for (size_t i = 0; i < n; i++)
{
for (size_t j = 0; j < n;)
{
char ch = fgetc(fout); //读取一个字符
if (ch == '0' || ch == '1')
{
a[i*n + j] = ch - '0';
j++;
}
else
{
continue;
}
}
}
fclose(fout);
}
0为通路，1为墙
然后我们将迷宫打印出来
void PrintMaze(int* a, size_t n)
{
for (size_t i = 0; i < n; i++)
{
for (size_t j = 0; j < n; j++)
{
cout << a[i*n + j] << " ";
}
cout << endl;
}
cout << endl;
}struct Pos
{
int _row;
int _col;
};bool MazePath(int* a, size_t n, Pos& entry, stack<Pos>& path)
{
Pos cur = entry;
path.push(cur); //当前位置压栈
while (!path.empty())
{
a[cur._row *n + cur._col] = 2; //走过的位置标记为2
Pos 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._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;
}
//上下左右都走不通，回退
cur = path.top();
path.pop();
if (cur._row == n - 1) // 出口
{
return true;
}
}
return false;
}判断当前位置的下一步是否走得通
bool CheckIsAccess(int* a, size_t n, Pos next)
{
assert(a);
if ((next._col >= 0) && (next._col < n) && (next._row >= 0) && (next._row < n) &&
(a[next._row *n + next._col] == 0))
{
return true;
}
else
return false;
}这样一个简单的迷宫就完成了，是不是看起来挺容易的呢？如果有不懂得地方，欢迎留言。有高见也欢迎留言~
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
