0

这是我现在使用 HashMap 实现的方法

private int steps=0;
private LinkedList<MazeCell> breadCrumbs = new LinkedList<MazeCell>();
private HashMap<MazeCell, Boolean> visitedCells = new HashMap<MazeCell, Boolean>();
public int stepsToSolveMaze(MazeCell cell)
{       
    if (visitedCells.get(cell) == null)
    {
        visitedCells.put(cell, true);
        breadCrumbs.push(cell);
    }

我正在使用递归算法来查找迷宫结束的步数。在我尝试迈出下一个“步骤”之前，我需要确保我没有去过我要迈出的地方。我觉得除了我去过的地方之外，还有比充满空值的 HashMap 更好的数据结构，但我真的不知道。有谁知道更好的数据结构？

4

4 回答 4

0

HashMap您应该使用HashSet而不是a 。代码会更容易阅读。由于 anHashSet由 an 支持，因此性能是等效的HashMap<E,Object>。

private int steps=0;
private LinkedList<MazeCell> breadCrumbs = new LinkedList<MazeCell>();
private Set<MazeCell> visitedCells = new HashSet<MazeCell>();
public int stepsToSolveMaze(MazeCell cell)
{       
    if (!visitedCells.contains(cell))
    {
        visitedCells.add(cell);
        breadCrumbs.push(cell);
    }   
}

一个HashSet offers constant time performance for the basic operations.

于 2013-03-18T15:13:01.423 回答
0

boolean[][]为整个矩阵设置一个怎么样？

如果您不处理太大的矩阵，我可能会选择这个选项。

1000x1000 不是那么大，整个矩阵将占用大约 1 MB 的存储空间（取决于实现）。

读/写的开销应该小于使用散列。还需要注意的是，如果散列函数不好，散列的性能可能会很糟糕。二维阵列解决方案没有这个缺点。

存储密集度较低的解决方案是BitSet[]1000x1000 矩阵的存储空间约为 125 KB。

请注意，您可以null在任何一种情况下（boolean[]或BitSet可以为空）都有值，其中有空行/列（取决于实现）以进一步减少存储空间。

免责声明：以上数字只是估计，我忽略了一些事情。

于 2013-03-18T15:36:53.357 回答
0

目前的设计还可以。如果单元格的数量是固定的，您可以将单元格保存在一个数组中，并使用位向量来表示访问过的单元格。例如，一个 32 位整数可以表示 32 个单元。

于 2013-03-18T15:14:12.933 回答
0

不相交集

这是实现这种数据结构的最有效方式。

简而言之，您所做的是创建一个代表您的迷宫的二维整数数组。数组中的每一行列将是迷宫中的 x,y 坐标。坐标位置上的值将显示它所在的“集合”。

因此，在您的情况下，如果您访问过某个位置，请在该位置放置 1。

因此，如果未访问坐标，它将包含 0。

于 2013-03-18T16:23:42.233 回答