JavaScriptを使用してボグルワードを検証する

問題

Boggleボードは、個々の文字の2D配列です。 −

const board = [
   ["I","L","A","W"],
   ["B","N","G","E"],
   ["I","U","A","O"],
   ["A","S","R","L"]
];

ボグルボードと文字列を取り込んで、その文字列がボグルボードで有効な推測であるかどうかを確認するJavaScript関数を作成する必要があります。有効な推測とは、隣接するセルを（水平、垂直、または斜めに）以前に使用したセルを再利用せずに。

たとえば、上記のボードでは、「LINGO」と「ILNBIA」はすべて有効な推測ですが、「BUNGIE」と「SINUS」はそうではありません。

例

以下はコードです-

const board = [
   ["I","L","A","W"],
   ["B","N","G","E"],
   ["I","U","A","O"],
   ["A","S","R","L"]
];
const guess = 'BINGO';
const checkWord = (board = [], guess = '') => {
   const numRows = board.length;
   const numCols = board[0].length;
   let queue = board.reduce((acc, row, i) => {
      row.forEach((x, j) => {
         if (x === guess[0]) {
            acc.push ( { pos: {r: i, c: j} , nextIndex: 1, path: [numCols*i + j ] } );
         }
      });
      return acc;
   }, []);
   let exploreWord = (obj, queue) => {
      let allMoves = [ {r: obj.pos.r - 1, c: obj.pos.c },
      {r: obj.pos.r + 1, c: obj.pos.c },
      {r: obj.pos.r, c: obj.pos.c - 1 },
      {r: obj.pos.r, c: obj.pos.c + 1 },
      {r: obj.pos.r - 1, c: obj.pos.c - 1 },
      {r: obj.pos.r - 1, c: obj.pos.c + 1 },
      {r: obj.pos.r + 1, c: obj.pos.c - 1 },
      {r: obj.pos.r + 1, c: obj.pos.c + 1 }];
      allMoves.forEach((o) => {
         let index = numCols * o.r + o.c;
         if (o.r >= 0 && o.r < numRows && o.c >= 0 && o.c < numCols) {
            if (board[o.r][o.c] === guess[obj.nextIndex] && !obj.path.includes(index)) {
               let cloneObj = JSON.parse(JSON.stringify(obj));
               cloneObj.pos = { r: o.r, c: o.c };
               cloneObj.nextIndex += 1;
               cloneObj.path.push(index);
               queue.push(cloneObj);
            }
         }
      });
   };
   while (queue.length > 0) {
      let obj = queue.shift();
      if (obj.nextIndex === guess.length) {
         return true;
      }
      exploreWord(obj, queue);
   }
   return false;
};
console.log(checkWord(board, guess));

コードの説明

私たちが取ったステップは-

• 2D配列をスキャンして、最初の文字の出現を見つけます

• 次に、{position、index}をキューにプッシュします。キューが空でないときに、最初のオブジェクトをポップアウトします

  。

• 次に、すべての方向を探します。セル内の文字が単語内の文字と一致し、セルが再利用されない場合は、{position、index}を更新し、それ以外の場合はキューに追加します。それ以外の場合は、オブジェクトを破棄し、一致するものが見つかるか、すべて一致しない場合に停止します。

出力

true