LCP 13 - 寻宝

二 题目

题目查看：https://leetcode-cn.com/problems/xun-bao/

/**
 * @param {string[]} maze
 * @return {number}
 */
var minimalSteps = function(maze) {

};

根据上面的已知函数，小伙伴们可以先尝试破解本题，确定了自己的答案后再看下面代码。

三 解题思路

/**
 * @param {string[]} maze
 * @return {number}
 * 求从起点到所有石头的最短步数,
 * 求各个机关到终点的最短步数
 * 求各个机关到各个石头的最短步数
 * 进而求出机关到机关的最短步数
 * 最后求出从起点出发到激活所有机关的最短步数
 * 最后求从起点出发激活所有机关 + 从最后一个机关到终点的最短步数
 * 一堆石头有无限个石头， 一个石头只能激活一个机关
 */
// 二位数组记录从某个点出发到其他点的最小步数
let dist = null
// 求dist的时候记录某个点是否够已经访问过
let visited = null
// 记录各个机关到各堆巨石的最小步数
let distM = null
// 记录从起点出发到各个石块的最小步数
let distS = null
// 机关经石头到各个机关的最小步数
let distBM = null
// 各个机关到终点的最小步数
let distT = null


// 记录各个机关到终点的最小步数
const dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]

// 所有机关
let puzzles = null
// 所有石堆位置
let stones = null

var minimalSteps = function(maze) {
    let stoneNum = 0
    let puzzleNum = 0
    let start = null
    let end = null
    const m = maze.length
    const n = maze[0].length
    stones = []
    puzzles = []
    distS = generateArray(m, n, -1)
    distT = generateArray(m, n, -1)
    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n; j++) {
            // 石头
            if(maze[i][j] === 'O') {
                stones.push([i, j])
                stoneNum++
                // 机关
            } else if(maze[i][j] === 'M'){
                puzzles.push([i, j])
                puzzleNum++
                // 起点
            } else if(maze[i][j] === 'S') {
                start = [i, j]
                // 终点
            } else if(maze[i][j] === 'T') {
                end = [i, j]
            }
        }
    }
    distM= generateArray(puzzleNum, stoneNum, -1)
    distBM = generateArray(puzzleNum, puzzleNum, -1)
    bfs(maze, start, m, n)
    if(puzzleNum === 0) return dist[end[0]][end[1]]

    // 求起点到各个石堆的最小步数
    for(let stone of stones) distS[stone[0]][stone[1]] = dist[stone[0]][stone[1]]
    bfs(maze, end, m, n)
    // 求终点到各个机关的最小步数
    for(let p of puzzles) distT[p[0]][p[1]] = dist[p[0]][p[1]]
    // 求各个机关到各个石堆的最小步数
    for(let i = 0; i < puzzleNum; i++) {
        bfs(maze, puzzles[i], m, n)
        for(let j = 0; j < stoneNum; j++) {
            distM[i][j] = dist[stones[j][0]][stones[j][1]]
        }
    }
    /**
     * 接下来求从起点出发开启所有机关, 最后一个机关是某个的最小步数,分量不，
     * 第一步求得从起点出发只开启一个机关的最小步数
     * 第二步根据第一步的结果生成从起点出发开启所有机关、最后一个开启的机关是某一个的最小步数
     */

    let all = 1 << puzzleNum
    // dp 是二维数组, 第一维二进制表示某一位为1表示这一机关是开启状态， 第二位只是最后开启的是哪个机关
    let dp = generateArray(all, 16, -1)
    for(let i = 0; i < puzzleNum; i++) {
        let idx = 1 << i
        let best = -1
        for(let j = 0; j < stoneNum; j++) {
            if((distS[stones[j][0]][stones[j][1]] === -1) || (distM[i][j] === -1)) continue
            let value = distS[stones[j][0]][stones[j][1]] + distM[i][j]
            if((best === -1) || value < best) best = value
        }
        dp[idx][i] = best
    }

    // 求出机关到机关之间经过巨石的最短步数, 因为一块石头只能开启一个机关
    for(let i = 0; i < puzzleNum; i++) {
        for(let j = 0; j < puzzleNum; j++) {
            if(i !== j) {
                let best = -1
                for(let k = 0; k < stoneNum; k++) {
                    if((distM[i][k] !== -1) && (distM[j][k] !== -1)) {
                        let value = distM[i][k] + distM[j][k]
                        if((best === -1) || (value < best)) best = value
                    }
                }
                distBM[i][j] = best
            } else distBM[i][j] = 0
        }
    }

    // 求出从起点出发激活所有机关、最后一个机关被激活的最小步数, 求得是dp[i][j]
    for(let i = 1; i < all; i++) {
        for(let j = 0; j < puzzleNum; j++) {
            // 每一轮只求j
            if(i & (1 << j)) {
                for(let k = 0; k < puzzleNum; k++) {
                    // j != k && (i & (1 << k)) && dp[i - (1 << j)][k] != -1 && distBM[k][j] != -1
                    // j 不等于k, k已被开启、j未被开启的情况存在, k、j之间有路径可达
                    if((j !== k) && (i & (1 << k)) && (dp[i - (1 << j)][k] !== -1) && (distBM[k][j] !== -1)) {
                        let value = dp[i - (1 << j)][k] + distBM[k][j]
                         // 谁小我就从谁过来
                        if((dp[i][j] === -1) || (value < dp[i][j])) dp[i][j] = value
                    }
                }
            }
        }
    }

    /**
     * 最后求开启所有机关最小步数 + 从一个机关到终点的最小步数的和的最小值,这个就是答案
     *
     */
    let ans = Infinity
    let left = all - 1 // that is 1111111111111111
    for(let i = 0; i < puzzleNum; i++) {
        if((dp[left][i] !== -1) && (distT[puzzles[i][0]][puzzles[i][1]] !== -1)) {
            let value = dp[left][i] + distT[puzzles[i][0]][puzzles[i][1]]
            if(value < ans) ans = value
        }
    }

    return ans === Infinity ? -1 : ans
};


function bfs(maze, entry, m, n) {

    dist = generateArray(m, n, -1)
    visited = generateArray(m, n , 0)

    let queue = [entry]
    visited[entry[0]][entry[1]] = 1
    dist[entry[0]][entry[1]] = 0
    let step = 0
    while(queue.length) {
        step++
        let len = queue.length
        for (let i = 0; i < len; i++) {
            let [x, y] = queue.pop()
            for (let dir of dirs) {
                let newX = x + dir[0]
                let newY = y + dir[1]
                if ((newX < 0) || (newX >= m) || (newY < 0) || (newY >= n) || visited[newX][newY] || (maze[newX][newY] === '#')) {
                    continue
                }
                dist[newX][newY] = step
                visited[newX][newY] = 1
                queue.unshift([newX, newY])
            }
        }
    }
}

function generateArray(m, n, fill){
    let arr = new Array(m)
    for(let i = 0; i < m; i++) arr[i] = new Array(n).fill(fill)
    return arr
}

四 统计分析

本题不需要统计分析。

五 套路分析

本题暂未发现任何套路，如果有但是 jsliang 后面发现了的话，会在 GitHub 进行补充。

jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。