string - 使用回溯在矩阵中查找单词

Question

我听说回溯可用于查找给定单词是否存在于二维字母矩阵中，但不知道如何实现它。例如，如果我们有一个像这样的矩阵：

G O P
N N A
A B E

规则是一个人可以从任何位置水平、垂直和对角移动，那么我们需要判断上面的矩阵是否包含“GONE”这个词。在这里，我们可以首先存储所有 G 的位置（如果存在 >1 G）并从每个位置开始检查，但是如何使用回溯进行检查？谢谢。

Answer 1

这个游戏叫做Boggle。这是关于它的一个很好的线程（包括代码示例）。

Answer 2

我将对算法进行伪编码

从你的单词中找到起始字母，开始使用该位置的回溯功能（传递下一个字母或 leeter 的下一个位置）

如果这是您正在寻找的最后一个位置，您会找到它。检查 N（北）处的字母是否是下一个字母，Ok 再次使用该位置（您现在所在的位置）和下一个字母（或下一个字母字符串中的位置）调用函数。如果不是在NE检查字母等等。如果您完成但没有找到合适的匹配项，请返回上一个呼叫。

HTH，如果您需要，请随时要求澄清。