1263.推箱子.md

1263.推箱子

/*
 * @lc app=leetcode.cn id=1263 lang=typescript
 *
 * [1263] 推箱子
 */

// @lc code=start
function minPushBox(grid: string[][]): number {}
// @lc code=end

解法 1: 记忆化搜索

function minPushBox(grid: string[][]): number {
  let m = grid.length,
    n = grid[0].length,
    end = 0,
    box = 0,
    player = 0
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 'S') {
        player = i * n + j
        grid[i][j] = '.'
      }
      if (grid[i][j] === 'B') box = i * n + j
      if (grid[i][j] === 'T') {
        end = i * n + j
        grid[i][j] = '.'
      }
    }
  }
  const dirs = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
  ]
  const check = (player: number, t: number) => {
    if (player === t) return true
    const target = [Math.floor(t / n), t % n]
    const queue = [[Math.floor(player / n), player % n]],
      vis: number[][] = Array.from({ length: m }, () => [])
    vis[queue[0][0]][queue[0][1]] = 1
    for (let [i, j] of queue) {
      for (let [di, dj] of dirs) {
        const x = di + i,
          y = dj + j
        if (x === target[0] && y === target[1]) return true
        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] !== '.' || vis[x][y]) continue
        vis[x][y] = 1
        queue.push([x, y])
      }
    }
    return false
  }
  let res = Infinity
  const cache: number[][] = Array.from({ length: m * n }, () => [])

  const dfs = (box: number, player: number, d: number) => {
    if (box === end) {
      res = Math.min(res, d)
      return
    }
    if (cache[box][player] !== undefined && cache[box][player] <= d) return
    cache[box][player] = d
    const i = Math.floor(box / n),
      j = box % n
    if (i > 0 && i < m - 1 && grid[i + 1][j] === '.' && grid[i - 1][j] === '.') {
      // 上下是空地,可以尝试上下推动
      //从上往下推
      if (check(player, box - n)) {
        grid[i][j] = '.'
        grid[i + 1][j] = 'B'
        dfs(box + n, box, d + 1)
        grid[i][j] = 'B'
        grid[i + 1][j] = '.'
      }
      // 从下往上推
      if (check(player, box + n)) {
        grid[i][j] = '.'
        grid[i - 1][j] = 'B'
        dfs(box - n, box, d + 1)
        grid[i][j] = 'B'
        grid[i - 1][j] = '.'
      }
    }
    if (grid[i][j + 1] === '.' && grid[i][j - 1] === '.') {
      // 左右是空的,可以尝试左右推动
      // 从左往右推
      if (check(player, box - 1)) {
        grid[i][j] = '.'
        grid[i][j + 1] = 'B'
        dfs(box + 1, box, d + 1)
        grid[i][j] = 'B'
        grid[i][j + 1] = '.'
      }
      // 从右往左推
      if (check(player, box + 1)) {
        grid[i][j] = '.'
        grid[i][j - 1] = 'B'
        dfs(box - 1, box, d + 1)
        grid[i][j] = 'B'
        grid[i][j - 1] = '.'
      }
    }
  }
  dfs(box, player, 0)
  return res === Infinity ? -1 : res
}

Case

test.each([
  {
    input: {
      grid: [['S'], ['B'], ['T'], ['.'], ['#']],
    },
    output: 1,
  },
  {
    input: {
      grid: [
        ['#', '.', '.', '#', '#', '#', '#', '#'],
        ['#', '.', '.', 'T', '#', '.', '.', '#'],
        ['#', '.', '.', '.', '#', 'B', '.', '#'],
        ['#', '.', '.', '.', '.', '.', '.', '#'],
        ['#', '.', '.', '.', '#', '.', 'S', '#'],
        ['#', '.', '.', '#', '#', '#', '#', '#'],
      ],
    },
    output: 7,
  },
  {
    input: {
      grid: [
        ['#', '#', '#', '#', '#', '#'],
        ['#', 'T', '#', '#', '#', '#'],
        ['#', '.', '.', 'B', '.', '#'],
        ['#', '.', '#', '#', '.', '#'],
        ['#', '.', '.', '.', 'S', '#'],
        ['#', '#', '#', '#', '#', '#'],
      ],
    },
    output: 3,
  },
  {
    input: {
      grid: [
        ['#', '#', '#', '#', '#', '#'],
        ['#', 'T', '#', '#', '#', '#'],
        ['#', '.', '.', 'B', '.', '#'],
        ['#', '#', '#', '#', '.', '#'],
        ['#', '.', '.', '.', 'S', '#'],
        ['#', '#', '#', '#', '#', '#'],
      ],
    },
    output: -1,
  },
  {
    input: {
      grid: [
        ['#', '#', '#', '#', '#', '#'],
        ['#', 'T', '.', '.', '#', '#'],
        ['#', '.', '#', 'B', '.', '#'],
        ['#', '.', '.', '.', '.', '#'],
        ['#', '.', '.', '.', 'S', '#'],
        ['#', '#', '#', '#', '#', '#'],
      ],
    },
    output: 5,
  },
])(
  'input: grid = $input.grid, param = $input.param, param = $input.param, param = $input.param, param = $input.param, param = $input.param',
  ({ input: { grid }, output }) => {
    expect(minPushBox(grid)).toEqual(output)
  },
)