很抱歉，如果这是一些线索的复制品，但我真的不知道如何描述这个问题。
我想知道什么是最小的数据结构，以防止2d网格旅行者重复自己（即旅行到它已经旅行过的某个点）。出行者每次只能水平或垂直移动1步对于我的特殊情况（下面），二维网格实际上是一个左下角的坐标轴，其中一个坐标永远不会超过另一个坐标轴。
例如，对于1d情况，这可以通过记录上一次行程的方向来简单地完成。如果方向改变了，它就在重复。
对于二维情况，它变得复杂。最简单的方法是创建一个记录以前旅行过的点的列表，但是我想知道有没有更有效的方法来做到这一点？
我正在为四和实现一个或多或少的“四指”算法，其中中间的两个手指朝两个方向移动（即i、j、k和l）：
i=> <=j=> <=k=> <=l
1 2 3 ... 71 72 ... 123 124 ... 201 202 203
手指移动的方向由某种算法决定（或建议），但可能导致永久循环。因此，如果中间的两个手指开始重复历史位置，我不得不强迫不要接受一些建议。
编辑
这些天来，我找到了两个解决方案。它们都不是解决这个问题的理想方案，但它们至少有些实用性：
正如@sorin在下面提到的，一个解决方案是保存一个表示所有单元格状态的位数组。对于这里的三角形网格示例，我们甚至可以压缩数组以将内存成本减少一半（尽管需要
k^2时间来计算位位置，其中k是自由度，即这里的2）标准数组只使用线性时间）。另一个解决办法是直接避免逆向行驶设置算法使
j和k只向一个方向移动（这可能是贪婪的）。但是，由于2D网格旅行者每次都有沿轴1步移动的良好特性，所以我想知道是否有更多的“专业化”表示。
为了这种运动。
谢谢你的帮助！
最佳答案
如果您正在寻找最佳查找复杂性，那么HASSET是最好的事情。您需要o（n）内存，但所有查找和插入都是o（1）。
如果您经常访问大多数单元格，那么您甚至可以跳过散列部分并存储一个位数组即为每个单元格存储一个位，然后检查相应的位是0还是1。这在内存上要紧凑得多（至少是32x，一位比一个int，但可能更多，因为您还跳过了在数据结构内部存储一些指针，64位）。
如果这仍然占用太多空间，可以使用bloom过滤器（link），但这会给您一些误报（告诉您您访问过一个单元格，但实际上您没有）。如果这是你可以生活的空间节省是相当大的。
其他结构如bsp或kd树也可以工作。一旦你到达了一个所有东西都是空闲的或被占用的点（忽略上三角中未使用的单元格），你就可以将所有这些信息存储在一个节点中。
这是很难推荐的，因为它的复杂性，它也可能会使用O（n）存储器在许多情况下，但具有较大的常数。所有的检查都是o（logn）。