• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            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
            日韩美女18网站久久精品| 精品久久久久久久中文字幕| 久久频这里精品99香蕉久| 亚洲精品无码久久久| 久久夜色精品国产噜噜噜亚洲AV| 国产精品久久99| 2021最新久久久视精品爱| 成人免费网站久久久| 久久福利资源国产精品999| 狠狠色丁香久久综合婷婷| 青青久久精品国产免费看| 久久中文骚妇内射| 欧美久久久久久午夜精品| 精品久久久久久国产潘金莲| 久久国产精品一区| 久久国产精品77777| 久久综合给合综合久久| 久久精品国产一区| 久久精品黄AA片一区二区三区| 久久久久人妻精品一区三寸蜜桃 | 久久99国产综合精品免费| 久久99精品九九九久久婷婷| 国产亚洲综合久久系列| 一本色道久久88—综合亚洲精品| 久久男人中文字幕资源站| 99久久精品久久久久久清纯| 久久成人国产精品| 久久天堂AV综合合色蜜桃网 | 久久青青草原精品国产| 少妇人妻综合久久中文字幕| 免费一级做a爰片久久毛片潮| 久久本道久久综合伊人| 久久99久久成人免费播放| 久久久综合九色合综国产| 久久99精品久久久久久| 72种姿势欧美久久久久大黄蕉 | 久久99精品久久久久久不卡 | 久久精品成人一区二区三区| 91精品日韩人妻无码久久不卡| 久久综合丝袜日本网| 久久精品中文字幕一区|