gpt4 book ai didi

c++ - 为迷宫实现一棵树以在 DFS、BFS 中使用

转载 作者:塔克拉玛干 更新时间:2023-11-02 23:37:59 30 4
gpt4 key购买 nike

我的程序从文件中获取一个字符数组作为输入。该数组如下所示:

"#########",
"# # #",
"# ## # #",
"# # #",
"### # ###",
"# # # #",
"# # #####",
"# # #",
"#########",

我正在实现 DFS 和 BFS 来解决这个从 [1,1] 开始并以 [width - 1,height - 1] 结束的迷宫。

我想制作一棵代表迷宫的树,然后分别使用每种算法遍历这棵树。

我将从每一行开始并扫描空单元格,在每个空单元格处,其右侧、左侧和底部的每个单元格都将成为该单元格的子单元格。它看起来像这样:

    for (int i = 0; i < width; i++)
{
for (int j = 0; j < height; j++)
{
if (isEmpty(maze[i][j]))
{
putChildren(maze[i-1][j], maze[i][j+1], maze[i+1][j]);
//this will check if it's a wall first
}
}

像这样实现树然后使用它通过 DFS 和 BFS 遍历树是否是一种可行的策略,或者我应该采用另一种方式吗?

最佳答案

不错的项目,我喜欢这样的事情。顺便说一下,您是否考虑过定向尝试算法(所谓的 A* 算法)我认为它对您来说会更好,尤其是在处理 2D 数组时。它在通常情况下比其他方法具有更好的性能,并且您不需要使用链接单元格。该算法也有一些改进,包括与“先尝试方向”方法链接的内存。当然你的方法没有问题,但考虑一下当你有非常巨大的矩阵要处理时的情况。

关于c++ - 为迷宫实现一棵树以在 DFS、BFS 中使用,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19820683/

30 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com