时间戳

首页 > 解决方案 > Crossoword Visualizer 广度优先搜索带方向

javascript - Crossoword Visualizer 广度优先搜索带方向

问题描述

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

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

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

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

例如，如果我的电路板如下所示：

Y A T
C E V
B X S

我需要寻找“YES”这个词，该算法在 [0][0] 处得到匹配并获取所有邻居（在本例中为 A、C、E）。然后它检查是否有任何匹配单词的第二个字符（这里是 E）。但是现在算法应该看到这个词是诊断性的，并且只返回对角线邻居（这里是 S）。

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

为了更好地理解，这是我到目前为止编写的代码：

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

当然，如果您有任何其他建议，我可以如何更精简/更有效地编写算法，我愿意接受所有反馈。

感谢您的帮助，不胜感激：）

标签： javascriptalgorithmbreadth-first-searchvisualizer

解决方案

我不会为此选择 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);
}

推荐阅读