773.js

/** ------------------------------------------------------------------------------
 * 
 * 773. Sliding Puzzle
 * Topics: BFS, Array
 * https://leetcode.com/problems/sliding-puzzle/description/?envType=daily-question&envId=2024-11-25
 * 
 ------------------------------------------------------------------------------ */
const mapping = {
  0: [1, 3],
  1: [0, 2, 4],
  2: [1, 5],
  3: [0, 4],
  4: [1, 3, 5],
  5: [2, 4],
}

/**
 * @param {number[][]} board
 * @return {number}
 */
var slidingPuzzle = function (board) {
  const swap = (state, pos, next) => {
    const array = state.split("")
    ;[array[pos], array[next]] = [array[next], array[pos]]
    return array.join("")
  }

  let state = ""
  board.forEach((row) => (state += row.join("")))

  const visited = new Set(state)

  const q = [[state, state.indexOf("0"), 0]]

  while (q.length) {
    const [state, pos, moves] = q.shift()

    if (state === "123450") {
      return moves
    }

    for (let next of mapping[pos]) {
      const newState = swap(state, pos, next)

      if (visited.has(newState)) {
        continue
      }

      visited.add(newState)
      q.push([newState, next, moves + 1])
    }
  }

  return -1
}

var slidingPuzzle = function (board) {
  let q = new Queue(),
    seen = new Set()
  q.push(board.flat().reduce((a, c, i) => a + (c << (3 * i)), 0))
  if (q.front() === 22737) return 0
  for (let turn = 1; !q.isEmpty(); turn++)
    for (let qlen = q.size(); qlen; qlen--) {
      let bnum = q.pop(),
        i = 0
      while (bnum & (7 << (3 * i))) i++
      for (let d = -3; d < 4; d += 2) {
        let id = i + d
        if (id < 0 || id > 5 || i % 3 === 1 + d) continue
        let x = (bnum >> (3 * id)) & 7,
          next = bnum - (x << (3 * id)) + (x << (i * 3))
        if (next === 22737) return turn
        if (!seen.has(next)) q.push(next), seen.add(next)
      }
    }
  return -1
}