773.滑动谜题

链接：773.滑动谜题
难度：Hard
标签：广度优先搜索、数组、矩阵
简介：给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。

题解 1 - typescript

• 编辑时间：2021-06-26
• 执行用时：192ms
• 内存消耗：50.8MB
• 编程语言：typescript
• 解法介绍：广度悠闲搜索，计算每次移动后的最小步数。

function slidingPuzzle(board: number[][]): number {
  const ANS_STR = '123,450';
  const stringify = (board: (number | string)[][]) => board.map(v => v.join('')).join(',');
  if (stringify(board) === ANS_STR) return 0;
  const parse = (boardStr: string) => boardStr.split(',').map(v => v.split(''));
  const getZeroIndex = (index: number): [number, number] =>
    index <= 2 ? [0, index] : [1, index - 4];
  const queue: string[] = [stringify(board)];
  const map = new Map<string, number>([[queue[0], 0]]);
  let ans = Infinity;
  const updateMap = (newStr: string, step: number) => {
    if (newStr === ANS_STR) ans = Math.min(ans, step + 1);
    else {
      map.has(newStr) || queue.push(newStr);
      map.set(newStr, Math.min(map.get(newStr) ?? Infinity, step + 1));
    }
  };
  const swap = (board: string[][], row1: number, col1: number, row2: number, col2: number) => {
    [board[row1][col1], board[row2][col2]] = [board[row2][col2], board[row1][col1]];
  };
  while (queue.length !== 0) {
    const boardStr = queue.shift()!;
    const step = map.get(boardStr)!;
    const [row, col] = getZeroIndex(boardStr.indexOf('0'));
    const board = parse(boardStr);
    if (row === 0) {
      swap(board, row, col, row + 1, col);
      updateMap(stringify(board), step);
      swap(board, row, col, row + 1, col);
    }
    if (row === 1) {
      swap(board, row, col, row - 1, col);
      updateMap(stringify(board), step);
      swap(board, row, col, row - 1, col);
    }
    if (col > 0) {
      swap(board, row, col, row, col - 1);
      updateMap(stringify(board), step);
      swap(board, row, col, row, col - 1);
    }
    if (col < 2) {
      swap(board, row, col, row, col + 1);
      updateMap(stringify(board), step);
      swap(board, row, col, row, col + 1);
    }
  }
  return ans === Infinity ? -1 : ans;
}