Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一个二维迷宫,#代表墙,@代表起点,字母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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理