1
class Solution:
2
    def shortestPathAllKeys(self, grid: List[str]) -> int:
3

4
        m = len(grid)
5
        n = len(grid[0])
6
        visited = set()
7

8
        steps = 0
9
        q = deque([])
10
        keyCt = 0
11

12
        for i in range(m):
13
            for j in range(n):
14
                if grid[i][j] == "@":
15
                    q.append((i, j, ""))
16
                elif grid[i][j].islower():
17
                    keyCt += 1
18

19
        while q:
20
            for _ in range(len(q)):
21
                curr_x, curr_y, keys = q.popleft()
22
                if (curr_x, curr_y, keys) in visited:
23
                    continue
24

25
                visited.add((curr_x, curr_y, keys))
26

27
                if len(keys) == keyCt:
28
                    return steps
29

30
                for x, y in ((0, 1), (1, 0), (-1, 0), (0, -1)):
31
                    nx = curr_x + x
32
                    ny = curr_y + y
33
                    if (
34
                        nx < 0
35
                        or ny < 0
36
                        or nx >= m
37
                        or ny >= n
38
                        or grid[nx][ny] == "#"
39
                        or (nx, ny, keys) in visited
40
                    ):
41
                        continue
42

43
                    curr = grid[nx][ny]
44
                    if curr in "abcdef" and curr not in keys:
45
                        q.append((nx, ny, keys + curr))
46
                    elif curr.isupper() and curr.lower() not in keys:
47
                        continue
48
                    else:
49
                        q.append((nx, ny, keys))
50
            steps += 1
51

52
        return -1