Golang 代码日的到来：搜索 XMAS 和 X-MAS

介绍

进入第四天，我们面前有一个网格问题，我们得到了一些网格形式的数字，即一些带有一些大写字母的行和列。我们需要做的是在任意方向（上、左、下、右、对角线）找到单词 XMAS，而在第二部分中我们需要找到形成 X 的单词 MAS。

那么，让我们看看如何在 golang 中解决这个问题。

您可以在 GitHub 上查看我的解决方案。

破坏先生 / 代码出现

代码的出现

构建网格

问题最根本的部分在于实际上将文本转换为网格或矩阵形式。我们可以将行分割成单独的行，并将每个字符作为列表中的元素附加，这样我们就可以得到一个字符串列表列表，它是一个矩阵或网格状（二维）结构。

所以，下面是谜题的输入。

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

我们需要将其转换成这样的

[
    [M M M S X X M A S M]
    [M S A M X M S M S A]
    [A M X S X M A A M M]
    [M S A M A S M S M X]
    [X M A S A M X A M M]
    [X X A M M X X A M A]
    [S M S M S A S X S S]
    [S A X A M A S A A A]
    [M A M M M X M M M M]
    [M X M X A X M A S X]
]

所以，这是一个字符串列表，我们可以在 golang 中说它是一个 [][]string 。我们可以通过创建这样的函数来做到这一点：

func ConstructGrid(lines []string) [][]string {
    grid := [][]string{}
    for _, line := range lines {
        row := []string{}
        for _, char := range strings.Split(line, "") {
            row = append(row, char)
        }
        grid = append(grid, row)
    }
    return grid
}

上面的函数接受一个字符串列表并返回一个字符串列表，这些字符串是网格中的单个字母。

我们可以读取文件字节并按换行符分割字节，然后将其用作此函数的输入。

因此，一旦输入被解析为网格，我们就可以开始思考在其中查找单词 XMAS 的实际逻辑。

第 1 部分

所以，在第一部分中，我们需要在矩阵中找到可能出现的单词 XMAS：

• 转发（作为 XMAS）

• 向后（如 SAMX）

• 向上
  

            S
            A
            M
            X

• 向下

            X
            M
            A
            S    

• 对角线向上（右或左上）

            S
              A
                M
                  X

            OR
                  S
                A
              M 
            X

• 对角线向下（右或左）

                     X
                   M
                 A
               S

            OR

            X
              M
                A
                  S

所以，XMAS 可以出现在网格中的方向有 8 个，这些 XMAS 的数量可能有 n 个。我们需要找到网格中这些的数量。

为了解决这个问题，我们可以找到单词 XMAS 中的第一个字符，然后逐个搜索所有方向并检查是否找到 M，如果在任何方向上找到 M，我们继续前进那个方向，检查那个方向是否有A和S。

方法如下：

• 将计数器初始化为 0

• 迭代每一行

  • 迭代行中的每个字符

    • 检查字符是否等于X

    • 如果角色是X→

      • 迭代所有方向（上、下、右、左、左上、右上、左下、右下）

        • 对于那个方向，如果我们发现字符是M
        • 继续向同一方向前进，类似地找到A和S，如果找到所有字符XMAS，则增加计数器
        • 否则选择循环中的另一个方向

这个看起来复杂又庞大，其实很简单，一次专注一件事，你就能轻松解决。

因此，为了实现这一点，我们需要首先定义一些东西：

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

因此，我们定义了方向上的整数列表，这些整数是我们需要添加或减去才能到达所需位置的 x 和 y 坐标。它基本上就像一个单位向量，它的距离为 1，方向由 或 表示 - 表示 x 坐标向左或向右移动，y 坐标上下移动。

所以，让我更清楚地解释一下，假设我位于 4x4 维度的网格中的 (1,2)。

[
    [M M M S X X M A S M]
    [M S A M X M S M S A]
    [A M X S X M A A M M]
    [M S A M A S M S M X]
    [X M A S A M X A M M]
    [X X A M M X X A M A]
    [S M S M S A S X S S]
    [S A X A M A S A A A]
    [M A M M M X M M M M]
    [M X M X A X M A S X]
]

所以，在 2,1 处我们有 G ，所以我们检查一些方向

向上 → 0,-1 → 2 0, 1-1 → 2,0，我们已经移动到 C

右 → 1,0 → 2 1, 1 0 → 3,1 ，我们已经移动到 H

下、左→ -1,1 → 2-1, 1 1 → 1, 2，我们已经移动到 J

所以，你明白了，我们正在使用这些坐标向某些方向移动。

我们可以使用它们来获得我们想要进行的下一个方向跳跃，以查找该元素是否具有我们正在搜索的单词中的下一个字符。

我们将编写一个函数来首先执行此操作，并抽象该函数来检查我们是否在网格中找到了该单词。

func ConstructGrid(lines []string) [][]string {
    grid := [][]string{}
    for _, line := range lines {
        row := []string{}
        for _, char := range strings.Split(line, "") {
            row = append(row, char)
        }
        grid = append(grid, row)
    }
    return grid
}

上面的函数接受一个网格并返回一个整数，该整数将作为分数，即在网格/矩阵中找到的 XMAS 单词数。

首先，我们需要迭代网格中的每一行，对于每一行，我们迭代字符，因此我们将 x 和 y 坐标作为网格的索引。然后我们需要检查当前字符是否是 X 或 wordList[0] ，如果是这种情况，我们迭代所有方向并检查是否可以找到 XMAS，即该方向上的 MAS，如果是，我们递增计数器。 FindXMAS 函数是什么，让我们将其抽象出来，并传入 x、y，它们是当前单词的坐标，1 将是 XMAS 的单词位置，在这种情况下，我们已经找到了我们需要的 X找到那个方向的 MAS。我们传递网格和方向，因此如果该方向中有 MAS，该函数将返回 true 或 false。

因此迭代：

• 我们迭代网格并获取 row 和 x 作为当前行的字符串列表和索引。

• 对于每一行，即字符串列表，我们迭代字符串列表以获取 char 和 y 作为字符（字符串）以及该字符在字符串列表中的索引。

• 如果我们发现当前字符等于 X，即 wordList 的第 0 个索引

  • 我们迭代所有方向并调用函数 FindXMAS 来检查剩余单词是否在该方向 MAS
  • 如果我们找到所有单词，我们就会增加计数器。

• 因此，我们在计算网格/矩阵中 XMAS 的单词数时返回计数器。

现在，我们可以实现 FindXMAS 函数，它接受 x、y 坐标、单词位置、方向和网格，如果找到单词则返回。

• 首先，我们获取当前的 x 坐标并添加方向的 x 分量（第 0 个索引或第一个元素）

• 将当前 y 坐标添加到方向的 y 分量（第一个索引或第二个元素）

• 如果当前函数中的单词位置，即单词索引或单词本身等于wordList，则表示已经完全找到了所需的单词

• 我们需要通过将方向添加到 x 和 y 坐标来检查，我们没有超出网格的宽度和高度，因此如果超出，我们将返回 false

• 最后的 if 用于检查当前字符是否等于我们要查找的单词，它可以是 M、A 或 S 。如果是这样，我们通过传递更新的 x 和 y 坐标以及 wordList 中的下一个单词来返回递归调用 FindXMAS 函数，我们保持方向相同并传递整个网格。
  

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

因此，我们已经实现了 FindXMAS 函数，如果我们通过更新坐标并检查网格中该位置的单词是否是 MAS 中的下一个单词，沿着特定方向找到 MAS 单词，则该函数将返回列表。

所以，这就是整个第一部分的样子：

[
    [M M M S X X M A S M]
    [M S A M X M S M S A]
    [A M X S X M A A M M]
    [M S A M A S M S M X]
    [X M A S A M X A M M]
    [X X A M M X X A M A]
    [S M S M S A S X S S]
    [S A X A M A S A A A]
    [M A M M M X M M M M]
    [M X M X A X M A S X]
]

我们将行作为字符串列表，并将其传递给 ConstructGrid 并获取网格，最后，我们调用 TraverseGrid ，通过传递网格并获取分数作为网格中 XMAS 单词的计数。

这是第 1 部分的内容。

第2部分

对于第二部分，我们需要找到十字形状的 MAS，如下所示：

func ConstructGrid(lines []string) [][]string {
    grid := [][]string{}
    for _, line := range lines {
        row := []string{}
        for _, char := range strings.Split(line, "") {
            row = append(row, char)
        }
        grid = append(grid, row)
    }
    return grid
}

所以，为了解决这个问题，我们可以采取类似的方法，但更简单，我们只需要找到 A，因为中心总是有 MAS 这个词，所以我们只需检查是否有 A 和左上角、右上角、右下角、左下角有 M 或 S 。

通过加1和减1得到右上角、左上位置、右下位置和左下位置的坐标。我们会进行基本检查，看看是否超出了网格的边界。如果我们超出界限，我们将找不到 MAS

但是如果我们在网格内，我们现在得到这 4 个位置的字符，我们检查左上角和右下角是否有 M 和 S 或 S 或 M，右上角和左下角类似分别具有M和S或S或M。这是字符 A 上方和下方的 M 和 S 的对角线搜索。

因此，如果我们的对角线都匹配，我们将返回 true。

            S
            A
            M
            X

这就是寻找 MAS 对角线的简单实现。

现在，我们需要稍微更改一下 TraverseGrid，因为我们只是迭代网格，并检查行中的字符中是否有 A，即 wordList[2]。现在，如果我们有 A，我们需要使用当前坐标和网格调用 FindMAS 函数，如果该函数返回 true，我们将增加计数器。

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

所以，这就是第2部分的最终实现，我们得到了横向MAS的计数。

您可以在 GitHub 上查看我的解决方案。

结论

所以，这就是 Golang 代码降临的第四天，如果您有任何建议，以及您是如何实现的，请告诉我。有更好的解决方案吗？

快乐编码:)

以上是Golang 代码日的到来：搜索 XMAS 和 X-MAS的详细内容。更多信息请关注PHP中文网其他相关文章！