寻宝

难度: Hard

我们得到了一副藏宝图，藏宝图显示，在一个迷宫中存在着未被世人发现的宝藏。

迷宫是一个二维矩阵，用一个字符串数组表示。它标识了唯一的入口（用 '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 。

Submission

运行时间: 1592 ms

内存: 46.6 MB

class Solution:
    def minimalSteps(self, maze: List[str]) -> int:
        # 先广度优先搜索找到所有能遇到的机关，石头，记录下标
        # 如果达不到终点或者机关，返回-1
        m, n = len(maze), len(maze[0])
        st,en,mm,oo = None,None, [],[]  # 起始 结束 机关 石头
        for i,row in enumerate(maze):
            for j,v in enumerate(row):
                if v == 'O': oo.append((i,j))
                elif v == 'M': mm.append((i,j))
                elif v == 'S': st = (i,j)
                elif v == 'T': en = (i,j)
        mm = [st]+mm  # 1.编码：起点+机关点的节点列表，两两之间必须经过石堆
        size = len(mm)
        dis = [[inf]*size for _ in range(size)]  # 2.计算两两之间步数：邻接矩阵，代表两两之间经过石堆的最短路
        def bfs(x,y):  # 以x,y为起点到其它所有点的最短路
            d = [[inf]*n for _ in range(m)]
            d[x][y] = 0 
            cur = [(x,y)]
            while cur:
                pre = cur
                cur = []
                for x, y in pre:
                    c = d[x][y] + 1
                    for a,b in (x-1,y),(x+1,y),(x,y-1),(x,y+1):
                        if 0<=a<m and 0<=b<n and maze[a][b] != '#' and c <d[a][b]:
                            d[a][b] = c 
                            cur.append((a,b))
            return d
        for x,y in oo:  # 枚举每个石堆为中间点，连接两个节点，找出每两个节点之间的最短路
            d = bfs(x,y)
            for i,(x,y) in enumerate(mm):
                for j,(a,b) in enumerate(mm):                    
                    dis[i][j] = min(dis[i][j],d[x][y]+d[a][b])

        mask = 1<<size 
        f = [[inf]*mask for _ in range(size)]  # 3.状压DP：f[i][j]表示状态j下，最后到达i的最短步数
        f[0][1] = 0
        for i in range(mask):  # 用刷表法转移
            if not i & 1:continue  # 不含起始点的状态不用讨论
            ones,zeros = [],[]  # 从所有1转移所有0
            for j in range(size):
                if i>>j&1: ones.append(j)
                else: zeros.append(j)
            for j in ones:  # 枚举从j
                if f[j][i] < inf:  # 可达状态才需要向后转移
                    for k in zeros:  # 转移到k
                        f[k][i|(1<<k)] = min(f[k][i|(1<<k)],f[j][i]+dis[j][k])
        
        x,y = en 
        d = bfs(x,y)  # 终点到每个位置的最短路，它和每个节点都是通的
        ans = min(f[i][-1] + d[x][y] for i,(x,y) in enumerate(mm)) # 4.转移到终点：尝试从每个节点直接到达终点的最短路
        return ans if ans < inf else -1

Explain

本题解采用了广度优先搜索（BFS）、动态规划以及状态压缩的策略。首先，通过广度优先搜索确定地图中起点、石头堆、机关和终点的位置。其次，使用 BFS 确定石头堆到每个点的最短路径，并据此建立起点和所有机关点的距离矩阵。然后，使用状态压缩的动态规划策略，记录在达到所有机关的各种状态下，到达每个机关的最小步数。最后，通过另一次 BFS 计算从终点到其他所有点的最短距离，并结合动态规划的结果确定能否拿到宝藏，并计算最小步数。

时间复杂度: O(O*M*N + 2^M * M^2 + M)

空间复杂度: O(M*N + M*2^M)

class Solution:
    def minimalSteps(self, maze: List[str]) -> int:
        m, n = len(maze), len(maze[0])
        st, en, mm, oo = None, None, [], []  # 初始化起点、终点、机关和石头堆
        for i, row in enumerate(maze):
            for j, v in enumerate(row):
                if v == 'O': oo.append((i, j))
                elif v == 'M': mm.append((i, j))
                elif v == 'S': st = (i, j)
                elif v == 'T': en = (i, j)
        mm = [st] + mm  # 加入起点到机关列表
        size = len(mm)
        dis = [[inf] * size for _ in range(size)]  # 初始化距离矩阵
        def bfs(x, y):  # BFS 函数定义
            d = [[inf] * n for _ in range(m)]
            d[x][y] = 0
            cur = [(x, y)]
            while cur:
                pre = cur
                cur = []
                for x, y in pre:
                    c = d[x][y] + 1
                    for a, b in ((x-1, y), (x+1, y), (x, y-1), (x, y+1)):
                        if 0 <= a < m and 0 <= b < n and maze[a][b] != '#' and c < d[a][b]:
                            d[a][b] = c
                            cur.append((a, b))
            return d
        for x, y in oo:  # 通过石堆优化距离矩阵
            d = bfs(x, y)
            for i, (x, y) in enumerate(mm):
                for j, (a, b) in enumerate(mm):
                    dis[i][j] = min(dis[i][j], d[x][y] + d[a][b])
        mask = 1 << size
        f = [[inf] * mask for _ in range(size)]  # 初始化动态规划表
        f[0][1] = 0
        for i in range(mask):  # 状态压缩DP
            if not i & 1: continue  # 忽略不包含起点的状态
            ones, zeros = [], []
            for j in range(size):
                if i >> j & 1: ones.append(j)
                else: zeros.append(j)
            for j in ones:
                if f[j][i] < inf:
                    for k in zeros:
                        f[k][i | (1 << k)] = min(f[k][i | (1 << k)], f[j][i] + dis[j][k])
        x, y = en
        d = bfs(x, y)  # 终点的BFS
        ans = min(f[i][-1] + d[x][y] for i, (x, y) in enumerate(mm))  # 计算最终结果
        return ans if ans < inf else -1

Explore

将起点加入到机关列表中是为了便于处理和简化算法的编程实现。在计算从起点到其他机关的最短路径时，如果起点本身就被视为一个机关的话，可以使用统一的方法来处理所有的点到点的路径计算，这样就不需要单独为起点编写特殊的代码。此外，这也方便了后面状态压缩动态规划的实现，因为起点在动态规划中作为初始状态，需要有一个明确的位置在状态数组中。

直接从机关到机关计算最短路径可能会遇到障碍物的问题，而通过石堆计算并更新距离可以有效地绕开这些障碍。石堆通常位于可以通过的关键路径上，利用石堆作为中转点，可以优化从一个机关到另一个机关的路径计算。这种方法可以在多个机关间找到较短的通道，尤其是在复杂的迷宫中，直接的机关到机关的路径可能并不是最优的。

在这个问题的动态规划解法中，状态压缩是通过一个整数的二进制表示来实现的。每个二进制位代表一个机关点是否已经被触发或到达。例如，如果有三个机关点，那么一个如'010'的二进制数表示中间的机关点已被触发或到达，而其他两个尚未处理。这样的状态压缩可以有效地表示所有机关的触发状态，使得状态转移可以通过位操作简洁地进行，极大地减少了状态的存储量和处理时间。