在Boggle棋盘上查找单词的算法

Question

我正在用vb .net做一个益智游戏。现在，我的骰子是一个二维数组(0, 0 ,1 )，等等。

我想让它做的是，当我输入单词时，它会使用button(x,y).doclick sub突出显示它在黑板上。现在，我的实现找到了第一个字母，然后继续尝试每个字母，直到它满足8角条件(即它与最后一个相邻)，但这并不总是有效。如果棋盘上有两个“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(回答，"o")，并获取网格中显示"go“的路径列表。再次突出显示第一个。