Xác thực từ Boggle trong JavaScript

Vấn đề

Bảng Boggle là mảng 2D các ký tự đơn lẻ, ví dụ:

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

Chúng ta cần viết một hàm JavaScript nhận vào bảng Boggle và một chuỗi, kiểm tra xem chuỗi đó có phải là đoán hợp lệ trong bảng Boggle hay không. Các đoán hợp lệ là chuỗi có thể tạo thành bằng cách nối các ô liền kề (ngang, dọc, chéo) mà không dùng lại ô đã dùng.

Ví dụ, trong bảng trên "LINGO" và "ILNBIA" là hợp lệ, trong khi "BUNGIE" và "SINUS" không.

Ví dụ

Dưới đây là mã nguồn:

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));

Giải thích mã

Các bước thực hiện:

• Quét mảng 2D tìm vị trí chữ cái đầu tiên của từ đoán.
• Đẩy { vị trí, chỉ số } vào hàng đợi, trong khi hàng đợi không rỗng, lấy đối tượng đầu tiên.
• Xét 8 hướng. Nếu chữ cái ô khớp với chữ cái trong từ và ô chưa dùng, cập nhật {vị trí, chỉ số} và thêm vào hàng đợi, ngược lại loại bỏ. Dừng khi tìm thấy khớp hoặc hết đường đi.

Kết quả

true