4

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

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

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

然后,如果它是 2X2,则一个单元格有四个单元格(子单元?),每个单元都与父单元双重链接。此外,这两个孩子是双重联系的。另外两个孩子也是。

从一个子单元格遍历到另一个子单元格意味着必须要么只跳转到下一个子节点链接(兄弟节点),要么先遍历回到父节点,然后再到另一个子节点链接对集中的目标子节点。(注意:树的想法只是我的想法,不是必需的)

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

这似乎很容易。但我就是无法理解模式创建逻辑:

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

此外,我可能不了解晶格单元的许多方面。我在互联网上进行了挖掘,试图找到一个关于为什么或如何有用的基本解释。我找到了一本关于逻辑基础的入门书:偏序集、幂集、自反性和基于这些原则的格图,例如哈斯图。

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

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

我正在寻找关于格子主题的良好入门/教程(因为它与编写 C++ 算法有关) ——希望能像典型的 Sam 在 21 天内自学 C++ 一样为我(从初学者开始)握住我的手, 或者其他的东西。由于晶格似乎是一个中级到非常高级的学科,这可能是不可能的。

如果不是教程,如果你们中的任何人都可以给我你在这个主题上的知识,我将不胜感激。

谢谢。

4

1 回答 1

1

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

于 2013-08-24T12:25:27.207 回答