c++ - 了解格子

Question

我一直在研究一个计算机科学问题，在第一次面试非常成功后，我在第二次面试代码测试中遇到了这个问题。否则，我会认为这是一个灌篮。

基本上，我要在 2 小时内使用晶格单元实现扫雷器。

如果是 1X1，则有一个单元格。

那么如果它是 2X2，一个单元格有四个单元格(子单元格？)，每个单元格都双向链接到父单元格。此外，这两个 child 相互之间存在双重联系。另外两个 child 也是。

从一个子单元格遍历到另一个子单元格意味着要么只跳到下一个子链接(一个兄弟)，要么首先遍历回到父单元格，然后到另一个子链接对集中的目标子单元格. (注:tree-idea只是我的想法，不是必须的)

我的总体想法是建立一个模式创建机制，然后根据深度参数隐含地变得越来越大。一种树结构似乎是最好的方法。

这看起来很简单。但我无法理解模式创建逻辑:

具有多个子节点的树结构很容易(八叉树、四叉树、二叉树等)，但是提出了一个优雅的系统，每当父节点产生多个子节点时，子节点也隐式链接到只有特定的 sibling 对我来说是一个令人费解的问题。所以，基本上，根据我的想法，根是格子图的中心，最远的子节点在边缘。

此外，我可能不了解晶格单元的许多方面。我在互联网上四处搜寻，试图找到一个关于为什么或如何有用的解释。我找到了一本关于该主题的入门读物，其中讨论了逻辑基础知识:偏序集、幂集、自反性以及基于这些原理的格图，例如哈斯图。

但是，这对我来说仍然不够好:没有 C++ 甚至伪代码示例。

我了解哈希表、链表、反向链表(递归/迭代)、二叉树(平衡/不平衡)、 vector 、字符串、反向等(所有基础知识)。三角函数，线性代数，四元数。一些计算。以及大量的图形编程技巧/技巧。我什至从头开始编写了两个游戏引擎，但简单的格子问题让我无所适从。我很尴尬。我想尽可能多地了解晶格，这样我再也不会像那样被烧毁了。但是，我需要的文档很难找到。

我正在寻找一本关于格子主题的好的入门书/教程(因为它与编写 C++ 算法有关)——希望能帮助我(从初学者开始)就像典型的 Sam 在 21 天内自学 C++ 之类的。由于格子似乎是一个中级到非常高级的主题，这可能是不可能的。

如果不是教程，如果你们中的任何人能告诉我你们在这个主题上有什么知识，我将不胜感激。

谢谢。

Answer 1

混淆源于对格这个词的误用:在数学中，格是一个偏序集，其中每两个元素都有一个 lub(最小上界)和一个 glb(最大下界)。游戏“树”(节点是棋盘的状态，由于树的独特路径属性，边缘移动显然没有任何 glb)，即使您加入通过不同的移动序列达到的相同状态(在这种情况下)树变成有向图)，如果从给定状态可以达到两个不同的最终状态，则不会有 glb。我已经十年没有玩扫雷了，但我的印象是可以这样结束游戏。因此，您需要考虑的底层数据结构是有向图(可能是无环图)，有时在数学意义上它是格子(忽略边上的方向)，但并非总是如此。