在 Boggle 板上查找单词的算法

Question

我正在用 vb .net 构建一个令人难以置信的游戏。 现在，我的骰子是一个二维数组（0,0 0,1）等...

我想要它做的是，当我输入这个词时，它使用 在棋盘上突出显示它Button(x,y).doclick 子突出显示它。 现在，我的实现找到第一个字母，然后继续尝试每个字母，直到它满足 8 个角条件（即它与最后一个字母相邻），但这并不总是有效。 如果板上有 2 个“G”，而我想要底部的一个，则这是行不通的。 有人能给我一个需要发生的事情的伪代码示例吗？ 我已经被难住了近 6 个小时试图解决这个问题。 谢谢

Answer 1

如果我理解正确的话，给定一个字符串，您想要突出显示与该字符串匹配的骰子的一条路径。 有时有多种可能的选择，因此添加字母可能会完全改变突出显示的内容。 保留前一个子字符串的结果可能是一个好方法，因此我们不必重新开始。 那么合理的做法是计算所有可能的路径。

给定字符串 s 的答案将是路径列表，其中路径是网格坐标列表。 每条路径都是您可以合理突出显示的内容，因此您只需突出显示第一个路径即可。 向字符串添加字母时，您会找到可以扩展的路径并删除无法扩展的路径。

恐怕我不知道怎么写vb代码。 既然你要求伪代码，这里有一些粗略的类似 python 的伪代码。 我正在将令人惊叹的网格编码为包含 16 个项目的列表。 Neighbors(x) 函数返回相邻位置的列表（边缘情况除外，即 [x-1, x+1, x-4, x+4]）。

def firstLetter(typed):
  answer = []
  for pos in range(16): if grid[pos]==typed: answer += [pos]
  return answer

def addletter(partialanswer, typed):
  answer2 = []
  for partial in partialanswer:
      for neighbor in neighbors(partial[-1]):
          if grid[neighbor]==typed: 
             # partial+[neighbor] is a list. answer2 is a list of such lists.
             answer2 += partial + [neighbor]
  return answer2

例如，如果玩家输入“go”，那么
(a) 玩家输入“g”，代码调用firstletter(“g”)并获取网格中包含“g”的位置的列表“答案”。 比如说，突出显示第一个。
(b) 玩家输入“o”，代码调用 addletter(answer,“o”) 并获取网格中显示“go”的路径列表。 再次强调第一个。