题目链接：https://leetcode-cn.com/problems/xun-bao/
参考链接：
https://leetcode-cn.com/problems/xun-bao/solution/xun-bao-bfs-dp-by-leetcode-solution/
我们得到了一副藏宝图，藏宝图显示，在一个迷宫中存在着未被世人发现的宝藏。
迷宫是一个二维矩阵，用一个字符串数组表示。它标识了唯一的入口（用 'S' 表示），和唯一的宝藏地点（用 'T' 表示）。但是，宝藏被一些隐蔽的机关保护了起来。在地图上有若干个机关点（用 'M' 表示），只有所有机关均被触发，才可以拿到宝藏。
要保持机关的触发，需要把一个重石放在上面。迷宫中有若干个石堆（用 'O' 表示），每个石堆都有无限个足够触发机关的重石。但是由于石头太重，我们一次只能搬一个石头到指定地点。
迷宫中同样有一些墙壁（用 '#' 表示），我们不能走入墙壁。剩余的都是可随意通行的点（用 '.' 表示）。石堆、机关、起点和终点（无论是否能拿到宝藏）也是可以通行的。
我们每步可以选择向上/向下/向左/向右移动一格，并且不能移出迷宫。搬起石头和放下石头不算步数。那么，从起点开始，我们最少需要多少步才能最后拿到宝藏呢？如果无法拿到宝藏，返回 -1 。
示例1：
输入： ["S#O", "M..", "M.T"]
输出：16
解释：最优路线为： S->O, cost = 4, 去搬石头 O->第二行的M, cost = 3, M机关触发 第二行的M->O, cost = 3, 我们需要继续回去 O 搬石头。 O->第三行的M, cost = 4, 此时所有机关均触发 第三行的M->T, cost = 2，去T点拿宝藏。 总步数为16。
示例2：
输入： ["S#O", "M.#", "M.T"]
输出：-1
解释：我们无法搬到石头触发机关
示例3：
输入： ["S#O", "M.T", "M.."]
输出：17
解释：注意终点也是可以通行的。
限制：
1 <= maze.length <= 1001 <= maze[i].length <= 100maze[i].length == maze[j].length- S 和 T 有且只有一个
- 0 <= M的数量 <= 16
- 0 <= O的数量 <= 40，题目保证当迷宫中存在 M 时，一定存在至少一个 O 。
- 看代码
- 思路比较简单，求出各项到各项的最短距离然后加起来，要考虑到边界情况和两个机关之间要取石头的情况
/**
* @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
}