Crossword Visualizer 广度优先搜索方向

Crossoword Visualizer Breadth first search with direction

我目前正在做我的一个小项目,一个填字游戏求解器。

给定 64 个字符的输入,算法将它们显示在 8x8 板上,然后继续查看是否有任何单词匹配。

到目前为止,我已经编写了一个算法,该算法针对每个单词循环遍历黑板上的字母,并检查其中是否有任何字母等于该单词的第一个字符。如果是这样,我调用一个辅助函数 returns 当前字符的所有邻居,并继续检查这些邻居中的任何一个是否等于单词的第二个字符,依此类推......所以基本上它是一种广度优先搜索算法,使用队列并将邻居推送到该队列:)

到目前为止这一切都很好,但我现在意识到,一旦算法匹配了单词的第二个字符,辅助函数应该只 return 具有相同方向的邻居。

例如,如果我的看板是这样的:

Y A T
C E V
B X S

并且我需要查找单词 'YES',算法在 [0][0] 处进行匹配并获取所有邻居(在本例中为 A、C、E)。然后它检查是否有任何匹配单词的第二个字符(这里是 E)。但是现在算法应该看到这个词在诊断上跟随并且只有 return 对角线邻居(这里是 S)。

您是否知道无需编写数千个 if 语句即可将此信息传递给辅助函数的优雅方法?

为了更好地理解,这是我目前编写的代码:

https://jsfiddle.net/jakob_mayerhofer/84xrfuwL/7/

当然,如果您对我如何高效地编写算法有任何其他建议leaner/more,我愿意接受所有反馈。

感谢您的帮助,感激不尽:)

我不会为此选择 BFS 算法,因为您已经知道要查找的单词的长度。当您需要在备选方案中找到 最短 路径时,您会选择 BFS,但这里从给定的起点(北、南、东、西)只有 4 种可能的备选方案, 它们的长度都相等。在这种情况下,你真的不需要图-搜索算法。

所以我会改变你的 crossWordSolver 的内部部分,并在 4 个可能的方向上使用一个循环,并且在每个方向上,立即沿着那个方向扫描直到单词的长度。

这是它的样子:

function crosswordSolver(words, grid) {
  let directions = [[-1, 0], [0, -1], [1, 0], [0, 1]];
  for (word of words) {
    let found = false;
    for (let i = 0; i < 8 && !found; i++) { // <-- extra exit condition
      for (let j = 0; j < 8 && !found; j++) { // <-- ... also here.
        if (grid[i][j] == word[0]) { // Simple check for 1st char
          for (let [dx, dy] of directions) { // Four directions to scan.
            found = true;
            for (let k = 0, x = i, y = j; k < word.length; k++, x+=dx, y+=dy) {
              if (x < 0 || y < 0 || x > 7 || y > 7 || word[k] !== grid[x][y]) {
                found = false; // Out of bounds, or mismatch
                break;
              }
            }
            if (found) break;
          }
        }
      }
    }
    if (found) checked.push(word);
  }
  console.log(checked);
}