实际上我的真正问题与迷宫没什么关系，但它可以很好地描述如下：
想象一下，站在迷宫中，墙壁沿着笛卡尔网格排列。墙壁不可见，有三种类型：
每一步都是从一个细胞到一个相邻细胞，我想确定每次移动会发生什么。
简单的解决方案：我使用坐标为我的网格，如下所示：
1 2 3 4 5 6 7
1 +---+---+---+
2 | | | |
3 +---+---+---+
我只保存坚固而致命的墙壁，而不是角落。连同墙的类型，这使得三倍：
(1,2,S), (1,4,S), (1,6,F), (2,1,S) ...
在每一个动作中，我都会计算出墙壁的位置，并在我的三重奏中查找它。 （2,2）到（2,4） - >位置（2,3）上有墙吗？
那么现在的问题是什么样的数据结构适合改善这一点？首先，我的坐标只有一半可以是墙壁，所以可以在这里减少。但空间可能是一个小问题。更重要的是提取信息的时间复杂度：如何在不通过简单解决方案的所有三元组的情况下轻松查找此结构中的墙类型以进行特定移动？澄清：下一步将始终从上一步结束开始。
附加信息：在我真正的问题中，迷宫最多只有3x3个单元格，而且只有一个房间没有任何墙壁站在房间内，只有围墙。我也有兴趣以JSON或XML格式以可读的方式保存迷宫，但这可能是一个不同的问题，因为它可能与原始问题的目标相冲突。
我认为对你的迷宫有用的是你的细胞的某种双向多链表，基本上是链接细胞的图表，你可以向所有方向移动。你的每个细胞都有四个方向的相邻细胞，它已链接到。
UP UP
LEFT RIGHT<->LEFT RIGHT
DOWN DOWN
在这里，RIGHT和LEFT是相邻细胞的链接，分别是细胞的位置。现在，您可以通过让单元格对象指向另一个单元格并同时为每个单元格指定四个墙壁来轻松完成此操作，您可以将其定义为您希望它们。这种方式允许您添加和删除迷宫中的单元格，以及使用简单的方法遍历迷宫。你如何定义你的细胞，显然是你自己的决定，但如果你想轻易导出它们，你可以给它们每个坐标。基本上这就是我将如何构建一个为您执行此操作的类：
Cell
Cell left, right, up, down //links to neighbors (can also be pointers)
Wall leftWall, rightWall, upWall, downWall //the walls of the cell
Coordinate coordinate //if needed
访问单元格的方法如下所示：
//go left
if leftWall is passable
go to left //e.g. return left cell
else if leftWall is deadly
end //or so
else
do stuff
如果您希望坐标轻松导出单元格，您可以在创建时分配它们，具体取决于您添加它们的位置，例如假设单元格位于（0,1）并使用方法addRight创建右侧单元格将新单元格的坐标自动设置为（0,2），因为单元格是“知道”它们的邻居，因为它们是链接的。
此外，通过使用一个对象/引用（即您当前的位置并将其更改为您要移动的对象/引用），可以轻松地从外部遍历链接列表。例如：
Cell currentCell = some cell
currentCell = currentCell.goLeft //checks if there is a wall to the left
如果没有墙，'currentCell'现在将保持对起始单元格左侧单元格的引用。
非常简单的表示是字节的NxM矩阵（二维阵列）。每个墙由两位表示。由于每个单元格有四个墙，因此您只需8位就可以存储所有四个墙。
将您的墙类型定义为：
wallTypeNone = 0;
wallTypeSolid = 1;
wallTypeFatal = 2;
wallTypeInvalid = 3; // should never see this
现在，将左侧墙壁映射到两个低位，顶部墙壁映射到位2和3，等等。
leftWallType = wallType & 0x03;
topWallType = (wallType >> 2) & 0x03;
rightWallType = (wallType >> 4) & 0x03;
bottomWallType = (wallType >> 6) & 0x03;
通过使用左列的隐式左侧墙和顶行的隐式顶墙，您可以节省大约一半的空间，代价是代码复杂度较低。然后一个单元“只拥有”两面墙：底部和右边。如果您想要单元格的左侧墙，则查询相邻单元格的右侧墙。如果你想要一个单元格的顶壁，你可以查询上面单元格的底部墙。这允许您以四位存储每个单元。因此，您的数组大小为N / 2 x M.查询左侧或顶部墙的速度稍慢（大约为纳秒级），因为它需要更多指令。但是你需要更少的内存访问来遍历整个迷宫。