Crossoword Visualizer Поиск в ширину с указанием направления - PullRequest
Новая
       21

Crossoword Visualizer Поиск в ширину с указанием направления

0 голосов
/ 16 февраля 2020

В настоящее время я работаю над небольшим моим проектом, кроссвордом Solver.

При вводе 64 символов алгоритм отображает их на доске 8х8, а затем продолжает поиск совпадения любого слова.

До сих пор я написал алгоритм, который для каждого слова просматривает буквы на доске и проверяет, равны ли какие-либо из них первому символу слова. Если это так, я вызываю вспомогательную функцию, которая возвращает всех соседей текущего символа и продолжает проверять, равны ли какие-либо из этих соседей второму символу слова и т. Д. Так что в основном это ширина в ширину Алгоритм поиска, использующий очередь и выдвигающий соседей в эту очередь:)

Пока это работает отлично, однако теперь я понял, что, как только алгоритм соответствует второму символу слова, функция помощника должна возвращать только сосед, который имеет то же направление.

например, если моя доска выглядит следующим образом: 

Y A T
C E V
B X S

, и мне нужно найти слово «ДА», алгоритм получает совпадение в [0] [0] и получает все окрестности (в данном случае A, C, E). Затем он проверяет, соответствуют ли какие-либо из них второму символу слова (здесь это E). Но теперь алгоритм должен видеть, что слово следует за диагнозом и возвращает только диагонального соседа (здесь S).

Знаете ли вы какой-нибудь элегантный способ передачи этой информации в функцию помощника без необходимости писать тысячи операторов if?

Для лучшего понимания вот код, который я написал до сих пор:

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

Конечно, если у вас есть какой-либо другой предложения, как я мог бы написать алгоритм экономнее / эффективнее Я открыт для всех отзывов.

Спасибо за вашу помощь, ценю это:)

1 Ответ

1 голос
/ 16 февраля 2020

Я бы не выбрал алгоритм BFS для этого, потому что вы уже знаете длину слова, которое нужно искать. BFS - это то, что вы выбрали бы, когда вам нужно найти кратчайший путь среди альтернатив, но здесь есть только 4 возможных альтернативы из данной начальной точки (север, юг, восток, запад), и все они имеют равную длину. В такой ситуации вам на самом деле не нужен алгоритм поиска графа *1003*.

Так что я бы изменил внутреннюю часть вашего crossWordSolver и использовал бы al oop поверх 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);
}
...