給出一個二維迷宮，#代表墻，@代表起點，字母a-f代表鑰匙，A-F代表對應的鎖（如果先拿到了鑰匙那么下次經過匹配的鎖的時候那一格就可以走），.代表空地，問最少多少步可以拿到所有鑰匙。
BFS，用位操作存儲已經獲得的鑰匙情況，且同時記錄已經走了幾步
1 #864
2 #Runtime: 305 ms (Beats 78.95%)
3 #Memory: 19.6 MB (Beats 36.84%)
4
5 class Solution(object):
6 def shortestPathAllKeys(self, grid):
7 """
8 :type grid: List[str]
9 :rtype: int
10 """
11 nkey = 0
12 n, m = len(grid), len(grid[0])
13 d = [(0, 1), (1, 0), (0, -1), (-1, 0)]
14 for i in range(n):
15 for j in range(m):
16 ch = grid[i][j]
17 if ch == '@':
18 sx, sy = i, j
19 if 'a' <= ch <= 'f':
20 nkey += 1
21 q = deque([(0, sx, sy)])
22 vis = defaultdict(bool)
23 vis[(0, sx, sy)] = True
24 stp = 0
25 while q:
26 sz = len(q)
27 while sz:
28 sz -= 1
29 ky, x, y = q.popleft()
30 if ky == (1 << nkey) - 1:
31 return stp
32 for i in d:
33 tx = x + i[0]
34 ty = y + i[1]
35 if 0 <= tx < n and 0 <= ty < m:
36 tp_ky = ky
37 ch = grid[tx][ty]
38 if ch == '#':
39 continue
40 if 'a' <= ch <= 'f':
41 tp_ky |= 1 << (ord(ch) - ord('a'))
42 if 'A' <= ch <= 'F' and not (ky & (1 << (ord(ch) - ord('A')))):
43 continue
44 if not vis[(tp_ky, tx, ty)]:
45 vis[(tp_ky, tx, ty)] = True
46 q.append((tp_ky, tx, ty))
47 stp += 1
48 return -1