909.蛇梯棋

链接：909.蛇梯棋
难度：Medium
标签：广度优先搜索、数组、矩阵
简介：N x N 的棋盘 board 上，按从 1 到 N*N 的数字给方格编号，编号 从左下角开始，每一行交替方向。返回达到方格 N*N 所需的最少移动次数，如果不可能，则返回 -1。

题解 1 - typescript

• 编辑时间：2021-06-27
• 执行用时：116ms
• 内存消耗：45.5MB
• 编程语言：typescript
• 解法介绍：广度优先搜索，储存后进行遍历。

function snakesAndLadders(board: number[][]): number {
  const N = board.length;
  const toBlock = (row: number, col: number) => {
    if ((N & 1) === 0) {
      return N * (N - 1 - row) + ((row & 1) === 0 ? N - col : col + 1);
    } else {
      return N * (N - 1 - row) + ((row & 1) === 0 ? col + 1 : N - col);
    }
  };
  const toBoard = (block: number): [number, number] => {
    const row = N - 1 - ~~((block - 1) / N);
    let col!: number;
    if ((N & 1) === 0) {
      col = (row & 1) === 0 ? N - 1 - ((block - 1) % N) : (block - 1) % N;
    } else {
      col = (row & 1) === 0 ? (block - 1) % N : N - 1 - ((block - 1) % N);
    }
    return [row, col];
  };
  const ANS_NUM = N ** 2;
  const map = new Map<number, number>([[1, 0]]);
  let ans = Infinity;
  const queue: [number, number][] = [[N - 1, 0]];
  while (queue.length !== 0) {
    const [row, col] = queue.shift()!;
    const block = toBlock(row, col);
    const step = map.get(block)!;
    if (ANS_NUM - block <= 6) {
      ans = Math.min(ans, step + 1);
      continue;
    }
    for (let i = 1; i <= 6; i++) {
      let nextBlock = block + i;
      let nextBoard = toBoard(nextBlock);
      const [nextRow, nextCol] = nextBoard;
      if (board[nextRow][nextCol] !== -1) {
        nextBlock = board[nextRow][nextCol];
        nextBoard = toBoard(nextBlock);
      }
      if (nextBlock === ANS_NUM) {
        ans = Math.min(ans, step + 1);
        continue;
      }
      if (!map.has(nextBlock)) queue.push(nextBoard);
      map.set(nextBlock, Math.min(map.get(nextBlock) ?? Infinity, step + 1));
    }
  }
  return ans === Infinity ? -1 : ans;
}