java - 4x4 单词网格 - Java

Question

如果一个单词存在于由随机字母 (A-Z) 组成的 4x4 网格中，您将如何进行搜索。有人可以引导我找到解决此问题的有效方法的正确方向吗？

条件如下:

• 单词由相邻的字母组成
• 单词可以水平、垂直或向左、向右或上下对角排列
• 单个单词中不得多次使用字母单元。

感谢各位的帮助!

Answer 1

您可以将其视为图形问题。将网格转换为图形，其中每个顶点代表网格中的一个单元格，顶点之间的边代表这些单元格之间的有效移动。

从那里，您可以使用以下递归算法来确定是否可以在图 G 中找到单词 S:

FindWord(G, S):
1. Set C to the first letter of S.
2. Set S' to S with the first letter removed.
3. For all vertices V in G:
  3.1. If the letter in V is not C, continue to the next vertex.
  3.2. If CheckPaths(G, S', V, {}) returns true, return true.
4. Return false.

CheckPaths(G, S, V, Visited):
1. If S is empty, return true.
2. Set C to the first letter of S.
3. Set S' to S with the first letter removed.
4. Set Visited' to Visited ∪ {V}.
5. For all cells V' connected to V:
  5.1. If V' ∈ Visited, continue to the next vertex.
  5.2. If the letter in V' is not C, continue to the next vertex.
  5.3. If CheckPaths(G, S', V', Visited') returns true, return true.
6. Return false.

实际的实现可能会有所不同(例如，最好不要复制 Visited，而是在确定路径失败后通过删除顶点来共享单个集合)，但这是基本的知道如何去做。