编程题1

[编程题]编程题1

热度指数：3957 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

有一个推箱子的游戏, 一开始的情况如下图:

上图中, '.' 表示可到达的位置, '#' 表示不可到达的位置，其中 S 表示你起始的位置, 0表示初始箱子的位置, E表示预期箱子的位置，你可以走到箱子的上下左右任意一侧, 将箱子向另一侧推动。如下图将箱子向右推动一格;

..S0.. -> ...S0.

注意不能将箱子推动到'#'上, 也不能将箱子推出边界;

现在, 给你游戏的初始样子, 你需要输出最少几步能够完成游戏, 如果不能完成, 则输出-1。

输入描述:

第一行为2个数字,n, m, 表示游戏盘面大小有n 行m 列(5< n, m < 50);
后面为n行字符串,每行字符串有m字符, 表示游戏盘面;

输出描述:

一个数字,表示最少几步能完成游戏,如果不能,输出-1;

示例1

输入

3 6
.S#..E
.#.0..
......

输出

算法知识视频讲解

Javascript_V8

牛客589890733号

一样的思路，不知道为什么会超时。。。

function solve(n, m, grid, initState, tx, ty) {
  const queue = [initState]
  const visited = new Array(n).fill(0).map(v => {
    return new Array(m).fill(0).map(v => {
      return new Array(n).fill(0).map(v => {
        return new Array(m).fill(0)
      })
    })
  })
  const isVisited = (state) => {
    return visited[state[0]][state[1]][state[2]][state[3]]
  }
  const setVisited = (state) => {
    visited[state[0]][state[1]][state[2]][state[3]] = 1
  }
  const getNextState = (state, choice) => {
    let [x, y, bx, by] = state
    x += choice[0]
    y += choice[1]
    if (x === bx && y === by) {
      bx += choice[0]
      by += choice[1]
    }
    if (grid[x] === undefined || grid[x][y] === undefined
      || grid[bx] === undefined || grid[bx][by] === undefined
      || grid[x][y] === 1 || grid[bx][by] === 1
    ) return null
    return [x, y, bx, by]
  }
  const isFinished = (state) => {
    return state[2] === tx && state[3] === ty
  }
  const choices = [[0, 1], [1, 0], [0, -1], [-1, 0]]
  let count = 1
  let depth = 0
  while (queue.length !== 0) {
    const curState = queue.shift()
    setVisited(curState)
    for (const choice of choices) {
      const nextState = getNextState(curState, choice)
      // 没有以更低的深度或者相同的深度访问过
      if (nextState !== null && !isVisited(nextState)) {
        if (isFinished(nextState)) {
          // 如果到达完成状态
          return depth + 1
        }
        queue.push(nextState)
      }
    }
    count--
    if (count === 0) {
      depth++
      count = queue.length
    }
  }
  return -1
}

let line = readline()
const initState = [0, 0, 0, 0]
const [n, m] = line.split(' ').map(v => parseInt(v))
const grid = new Array(n).fill(0).map(v => new Array(m).fill(0))
let tx = 0
let ty = 0
for (let i = 0; i < n; i++) {
    line = readline()
    for (let j = 0; j < m; j++) {
        switch (line[j]) {
            case '.':
                break
            case 'S':
                initState[0] = i
                initState[1] = j
                break
            case '#':
                grid[i][j] = 1
                break
            case 'E':
                tx = i
                ty = j
                break
            case '0':
                initState[2] = i
                initState[3] = j
        }
    }
}
console.log(solve(n, m, grid, initState, tx, ty))

发表于 2022-02-09 21:28:22 回复(0)