共计 4864 个字符，预计需要花费 13 分钟才能阅读完成。
LCP 13. 寻宝
题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/xun-bao
题目
咱们失去了一副藏宝图，藏宝图显示，在一个迷宫中存在着未被世人发现的宝藏。
迷宫是一个二维矩阵，用一个字符串数组示意。它标识了惟一的入口（用 ‘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 <= 100
- 1 <= maze[i].length <= 100
- maze[i].length == maze[j].length
- S 和 T 有且只有一个
- 0 <= M 的数量 <= 16
- 0 <= O 的数量 <= 40，题目保障当迷宫中存在 M 时，肯定存在至多一个 O。
解题思路
思路：状态压缩动静布局
先大抵说下题意，题目中要求咱们在迷宫中，从终点 S 走到起点 T。然而，迷宫中有一些规定以及限度：
- ‘#’：示意墙壁，
- ‘.’：示意可通行
- ‘M’：示意机关点，须要重石触发
- ‘O’：示意石堆，一次挪动只能搬动一个石头。石堆中的重石有限。
其中，要达到起点 T 须要将所有机关点 M 都被触发，求起码步数达到起点。
题目中阐明，人物可进行四个方位的挪动。依据下面的题意简介，那么可能呈现的状况如下（字符含意见上）：
- 从终点 S 达到 O 因为无奈间接从 S 到 M 因为触发机关 M 须要重石；
- 从 O 到 M 搬重石触发机关
- 从 M 再到 O 持续搬重石（假如前面还有机关）
- 从 M 到起点 T 当所有机关都触发，能够到起点。
题目要咱们求起码步数达到起点，也就是说，咱们能够思考将下面可能呈现的状况，将两个点之间的最短距离计算出来用以后续计算。
在这里，首先要先解决的是采取怎么的路线去取重石和触发机关。这里先进行大抵的剖析：
先看下面列举的可能状况，开始肯定是从 S 登程，通过某个 O，获得重石，而后达到某个 M，触发机关。在这里，对于某个特定的 M 来说，肯定存在某个 O，使得 S 通过 O 达到 M 的间隔最短。也就说，固定 M，枚举 O，就能够求得 S 达到每个 M 的最短距离。
机关点 M，有可能存在不止一个。那么达到某个 M 之后，还须要再次去某个 O 点获得重石再去其余 M 点触发机关，直至所有机关都被触发。在这里，假如先达到 M1，要取重石触发机关 M2，那么同样，能够枚举 O，求得 M1 达到 M2 的最短距离。
当所有的机关都触发了，那么剩下的就是从 M 达到 T 的间隔，这样同样能够计算出来。
下面是大抵的剖析，计算一一状况下的最短距离，进而求得整体的最短距离。然而这里有个须要留神的中央，因为须要所有的机关点 M 都被触发，那么触发 M 的程序不同时，那么将会导致后果不同。
依据后面的剖析，在给定的迷宫 maze 中，无论是否触发机关，每个地位到其余任意地位的间隔是不会扭转的。那么用 BFS 的思路计算点到点之间的间隔。
定义二维数组，保留机关 Mi 到 Mj 的最短距离，这里枚举所有的石头堆 O 进行计算。
定义 dp，利用二进制模式的 mask 示意状态，dpmask 示意以后处于第 i 个 M 的地位，以后的状态为 mask 的最短距离。机关的状态有两种：已触发和未触发。
当所有的机关都触发，那么从最初被触发的机关点登程，返回起点，比拟得出最短距离。
具体实现代码如下（含正文）。
代码实现
from typing import List
class Solution:
def minimalSteps(self, maze: List[str]) -> int:
# 四个方位
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
m = len(maze)
n = len(maze[0])
# 终点，起点
start_x, start_y, end_x, end_y = -1, -1, -1, -1
# 机关，石堆
buttons = []
stones = []
# 先将迷宫中字符所代表的意义进行标记
for i in range(m):
for j in range(n):
if maze[i][j] == 'M':
buttons.append((i, j))
elif maze[i][j] == 'O':
stones.append((i, j))
elif maze[i][j] == 'S':
start_x = i
start_y = j
elif maze[i][j] == 'T':
end_x = i
end_y = j
# 机关以及石堆数
num_b = len(buttons)
num_s = len(stones)
# 计算出发点到其余所有地位的间隔
start_to_any_pos = self.bfs(start_x, start_y, maze, m, n, directions)
# 如果没有石堆，那么就是间接找出出发点到起点的最短距离
if num_b == 0:
return start_to_any_pos[end_x][end_y]
# 定义数组，记录其中一个机关到另外一个机关以及到终点，起点的间隔
# dist[i][num_b] 示意到终点的间隔，dist[i][num_b+1] 示意到起点的间隔
dist = [[-1] * (num_b + 2) for _ in range(num_b)]
# 迷宫中，机关 M 可能有多个。先计算触发机关后，每个 M 达到起点的间隔
# im 记录机关到其余点的间隔
button_to_any_pos = []
for i in range(num_b):
b_x, b_y = buttons[i]
# 计算第 i 个机关 M 到其余点的间隔，存入 button_to_any_pos 中
button_to_any_pos.append(self.bfs(b_x, b_y, maze, m, n, directions))
# 机关到起点的间隔
dist[i][num_b+1] = button_to_any_pos[i][end_x][end_y]
# 计算出发点到每个机关的间隔
for i in range(num_b):
# S 到 M 的间隔
start_to_m = -1
for j in range(num_s):
s_x, s_y = stones[j]
# 固定某个机关，计算出发点 S 通过每个石堆达到机关的间隔
# 也能够了解为机关到起始点 S 的间隔，由变量 button_to_any_pos 存储
if button_to_any_pos[i][s_x][s_y] != -1 and start_to_any_pos[s_x][s_y] != -1:
# 计算间隔，比拟取小值
tmp = button_to_any_pos[i][s_x][s_y] + start_to_any_pos[s_x][s_y]
if start_to_m == -1 or start_to_m > tmp:
start_to_m = tmp
# 将此时 S 到 M 的最短距离存入 dist 数组中
dist[i][num_b] = start_to_m
# 这里计算第 i 个机关到第 j 个机关的间隔
# 例如：M1 通过 O 达到 M2 的最短距离
for j in range(i+1, num_b):
m_to_another_m = -1
for k in range(num_s):
s_x, s_y = stones[k]
if button_to_any_pos[i][s_x][s_y] != -1 and button_to_any_pos[j][s_x][s_y] != -1:
tmp = button_to_any_pos[i][s_x][s_y] + button_to_any_pos[j][s_x][s_y]
if m_to_another_m == -1 or m_to_another_m > tmp:
m_to_another_m = tmp
# 因为间隔是无向图，那么两点之间的间隔是对称的
dist[i][j] = m_to_another_m
dist[j][i] = m_to_another_m
# 如果一个机关，从出发点无奈达到，或者从机关点登程无奈到起点，阐明无门路，返回 -1
for i in range(num_b):
if dist[i][num_b] == -1 or dist[i][num_b+1] == -1:
return -1
# 定义 dp 数组，-1 示意为被遍历的状态
# 假如有 n 个 M，机关的状态有 2^n 个状态
# dp[mask][i] 示意以后处于第 i 个 M 的地位，以后的状态为 mask 的最短距离
dp = [[-1] * num_b for _ in range(1<<num_b)]
# 用二进制的模式示意 mask
# 初始化，从 S 到第 i 个机关，此时 mask 的第 i 位为 1，其余为 0
# 将后面计算的值赋值给 dp 数组
for i in range(num_b):
dp[1<<i][i]=dist[i][num_b]
# 开始遍历，计算 mask 不同状态，每个机关点 i 的值
# mask 索引从 1 开始
for mask in range(1, (1<<num_b)):
for i in range(num_b):
# 如果以后 dp 非法
if mask & (1<<i) != 0:
for j in range(num_b):
# 抉择下一个机关 j，要 j 还未触发，此时 mask 的 j 地位应该为 0
if mask & (1<<j) == 0:
next_mask = mask | (1<<j)
tmp = dp[mask][i] + dist[i][j]
if dp[next_mask][j] == -1 or dp[next_mask][j] > tmp:
dp[next_mask][j] = tmp
# 这里计算全副触发后，最初一个机关达到起点的间隔，取小值
ans = -1
final_mask = (1<<num_b) - 1
for i in range(num_b):
tmp = dp[final_mask][i] + dist[i][num_b+1]
if ans == -1 or ans > tmp:
ans = tmp
return ans
def bfs(self, x, y, maze, m, n, directions):
"""计算点 (x, y) 到其余点之间的间隔"""
res = [[-1] * n for _ in range(m)]
# 设点 (x, y) 为终点
res[x][y] = 0
from collections import deque
queue = deque()
queue.append([x, y])
while queue:
# 出队，计算点到点之间的间隔
cur_x, cur_y = queue.popleft()
# 限度边界，往四个方位挪动，遇到可通行且未被拜访，则进行挪动，记录间隔
for dx, dy in directions:
nx = cur_x + dx
ny = cur_y + dy
if 0 <= nx < m and 0 <= ny < n and maze[nx][ny] != '#' and res[nx][ny] == -1:
res[nx][ny] = res[cur_x][cur_y] + 1
queue.append([nx, ny])
return res
maze = ["S#O", "M..", "M.T"]
solution = Solution()
solution.minimalSteps(maze)实现后果
欢送关注
公众号【书所集录】
