博客

今天是一道难题！！！折磨了我好久！！！

如题：

 算法思想：

我们可以用一个三元组 (x,y,mask)表示当前的状态，其中 (x,y)表示当前所处的位置，mask是一个二进制数，长度恰好等于网格中钥匙的数目，mask的第 i个二进制位为 1，当且仅当我们已经获得了网格中的第 i把钥匙。

这样一来，我们就可以使用上述的状态进行广度优先搜索。初始时，我们把 (sx,sy,0)加入队列，其中 (sx,sy) 为起点。在搜索的过程中，我们可以向上下左右四个方向进行扩展：

-如果对应方向是空房间，那么 mask的值不变；

-如果对应方向是第 i把钥匙，那么将 mask 的第 i位置为 1；

-如果对应方向是第 i把锁，那么只有在 maskk 的第 i 位为 1 时，才可以通过。

当我们搜索到一个 mask每一个二进制都为 1 的状态时，说明获取了所有钥匙，此时就可以返回最短路作为答案。

代码：

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]#这个数组，避免了向四个方向每次都要加减的冗余情况，直接for x，y in dirs，然后加这个x，y就行了

        m, n = len(grid), len(grid[0])
        sx = sy = 0
        key_to_idx = dict()
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "@":
                    sx, sy = i, j
                elif grid[i][j].islower():#islower()  判断是否为小写字母
                    if grid[i][j] not in key_to_idx:
                        idx = len(key_to_idx)
                        key_to_idx[grid[i][j]] = idx

        q = deque([(sx, sy, 0)])#定义双端队列
        dist = dict()
        dist[(sx, sy, 0)] = 0
        while q:
            x, y, mask = q.popleft()
            for dx, dy in dirs:#向上下左右广度探索
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != "#":
                    if grid[nx][ny] == "." or grid[nx][ny] == "@":
                        if (nx, ny, mask) not in dist:
                            dist[(nx, ny, mask)] = dist[(x, y, mask)] + 1
                            q.append((nx, ny, mask))
                    elif grid[nx][ny].islower():
                        idx = key_to_idx[grid[nx][ny]]
                        if (nx, ny, mask | (1 << idx)) not in dist:
                            dist[(nx, ny, mask | (1 << idx))] = dist[(x, y, mask)] + 1
                            if (mask | (1 << idx)) == (1 << len(key_to_idx)) - 1:
                                return dist[(nx, ny, mask | (1 << idx))]
                            q.append((nx, ny, mask | (1 << idx)))
                    else:
                        idx = key_to_idx[grid[nx][ny].lower()]
                        if (mask & (1 << idx)) and (nx, ny, mask) not in dist:
                            dist[(nx, ny, mask)] = dist[(x, y, mask)] + 1
                            q.append((nx, ny, mask))
        return -1

运行结果：

好啦，今天的打卡艰难完成！！！