理解格

Question

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

基本上，我要在2小时内用格子细胞来完成扫雷。

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

如果是2X2，那么一个细胞就有四个单元(子单元？)，每个单元格都与父单元有双重链接。另外，这两个孩子是双重联系的。另外两个孩子也是。

从一个子单元单元遍历到另一个子单元将意味着必须跳到下一个chid链接(兄弟姐妹)，或者首先遍历回父单元，然后在另一个子链接对集中返回到目标子单元。(注:树的想法只是我的想法，不是我的要求)

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

这似乎很容易。但我无法理解模式创造的逻辑：

有多个孩子的树结构是很容易的(八叉树、四叉树、二叉树等)，但是想到了一个优雅的系统，当父母生下多个孩子时，孩子们也隐式地与特定的兄弟姐妹联系在一起，这对我来说是一个心理障碍。所以，基本上，根据我的想法，根是点阵图的中心，最远的子节点在边上。

此外，可能有许多方面的晶格细胞，我不明白。我在互联网上搜索，试图找到一个基本的解释，为什么或如何这是有用的。我找到了一本关于逻辑基础的入门文章:偏序集、powerset、自反性和基于这些原理的格图，例如Hasse图。

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

我理解哈希表、链表、反向链表(递归/迭代)、二叉树(平衡/不平衡)、向量、字符串、反转等等(所有基本知识)。三角，线性代数，四元数。一些Calc。以及大量的图形编程技巧/技术。我甚至从零开始写了两个游戏引擎，但是简单的格子问题让我无法理解。我很难为情。我想尽可能多地学习关于晶格的知识，这样我就再也不会像现在这样被烧死了。然而，我需要的文档很难找到。

我正在寻找一本关于格(因为它涉及到写算法)的好入门/教程--希望它能帮我(从初学者开始)抓住我的手，就像一个典型的山姆在21天内自学C++之类的。由于格似乎是一个中间到非常先进的学科，这可能是不可能的。

如果不是一本教程，如果你们中的任何一个人能给我一些关于这个问题的知识，我会非常感激的。

谢谢。

Answer 1

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