1
/**
2
 * @param {number[][]} board
3
 * @return {number}
4
 */
5

6
class BoardState {
7
  constructor(board, currStep) {
8
    this.board = this.copyBoard(board);
9
    this.boardString = this.flatToString(board);
10
    this.emptyIndex = this.findIndexOf0(board);
11
    this.currStep = currStep;
12
  }
13
  findIndexOf0(board) {
14
    for (let i = 0; i < board.length; i++) {
15
      for (let j = 0; j < board[i].length; j++) {
16
        if (board[i][j] === 0) return [i, j];
17
      }
18
    }
19
    return null;
20
  }
21
  copyBoard(board) {
22
    const newBoard = [];
23
    board.forEach((row) => {
24
      newBoard.push([...row]);
25
    });
26
    return newBoard;
27
  }
28
  flatToString(board) {
29
    let str = "";
30
    for (let i = 0; i < board.length; i++) {
31
      for (let j = 0; j < board[i].length; j++) {
32
        str += board[i][j];
33
      }
34
    }
35
    return str;
36
  }
37
}
38
var slidingPuzzle = function (board) {
39
  let queue = [new BoardState(board, 0)];
40
  let set = new Set();
41
  const x = board.length,
42
    y = board[0].length;
43
  const switchMoves = [
44
    [1, 0],
45
    [0, 1],
46
    [-1, 0],
47
    [0, -1],
48
  ];
49
  let slide = (i, j, newi, newj, currBoardState) => {
50
    if (newi < 0 || newj < 0 || newi >= x || newj >= y) {
51
      return null;
52
    }
53
    const newBoard = currBoardState.copyBoard(currBoardState.board);
54
    const temp = newBoard[i][j];
55
    newBoard[i][j] = newBoard[newi][newj];
56
    newBoard[newi][newj] = temp;
57
    const newBoardState = new BoardState(newBoard, currBoardState.currStep + 1);
58
    return newBoardState;
59
  };
60
  while (queue.length > 0) {
61
    const currBoardState = queue.shift();
62
    set.add(currBoardState.boardString);
63
    if (currBoardState.boardString === "123450") {
64
      return currBoardState.currStep;
65
    }
66
    const [i, j] = currBoardState.emptyIndex;
67
    switchMoves.forEach((move) => {
68
      const newBoardState = slide(
69
        i,
70
        j,
71
        i + move[0],
72
        j + move[1],
73
        currBoardState
74
      );
75
      if (newBoardState && !set.has(newBoardState.boardString)) {
76
        queue.push(newBoardState);
77
      }
78
    });
79
  }
80
  return -1;
81
};