• <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
            一個1000000*1000000的二維平面,中間有一些格子是障礙物(由blocked數組給出),給出起點和終點,問能否通過每步走東南西北中的一個方向一步來到達
            直接搜整個平面會TLE,但由題目描述可知最多只有200個障礙物,由Discussion()得到啟發,最多只要搜len(blocked)步長就可以得知起點或者終點有沒有被完全阻擋,只要從起點和終點開始各BFS len(blocked)步長即可

             1 #1036
             2 #Runtime: 2870 ms
             3 #Memory Usage: 26.5 MB
             4 
             5 class Solution(object):
             6     def BFS(self, source, target):
             7         m, n = 1000000, 1000000
             8         d = [[0, 1], [1, 0], [0, -1], [-1, 0]]
             9         q = deque([[source[0], source[1], 0]])
            10         vis = set()
            11         vis.add((source[0], source[1]))
            12         while q:
            13             x, y, stp = q.popleft()
            14             if stp > len(self.blocked) or [x, y] == target:
            15                 return True
            16             for dx, dy in d:
            17                 tx = x + dx
            18                 ty = y + dy
            19                 if 0 <= tx < 10**6 and 0 <= ty < 10**6 and (tx, ty) not in vis and (tx, ty) not in self.blocked:
            20                     vis.add((tx, ty))
            21                     q.append([tx, ty, stp + 1])
            22         return False
            23                     
            24     def isEscapePossible(self, blocked, source, target):
            25         """
            26         :type blocked: List[List[int]]
            27         :type source: List[int]
            28         :type target: List[int]
            29         :rtype: bool
            30         """
            31         self.blocked = {tuple(p) for p in blocked}
            32         return self.BFS(source, target) and self.BFS(target, source)
            日产精品久久久一区二区| 欧美午夜精品久久久久久浪潮| 久久精品综合一区二区三区| 久久精品国产亚洲精品| 国产精品激情综合久久| 手机看片久久高清国产日韩 | 久久久久亚洲AV成人网人人网站| 精品人妻伦九区久久AAA片69| 午夜精品久久久久久毛片| 国产一区二区精品久久岳| 久久久久国产精品三级网| 久久伊人精品一区二区三区| 狠狠人妻久久久久久综合蜜桃| 亚洲欧美一级久久精品| 国产成人综合久久精品尤物| 伊人久久大香线蕉综合热线| 91精品国产综合久久香蕉| 无码人妻精品一区二区三区久久 | 亚洲欧美国产精品专区久久| 蜜臀av性久久久久蜜臀aⅴ麻豆 | 亚洲精品国产第一综合99久久| 九九久久自然熟的香蕉图片| 精品久久久久久无码不卡| 国产成人精品久久免费动漫| 亚洲精品美女久久777777| 91精品国产色综久久| 久久无码人妻一区二区三区午夜 | 久久笫一福利免费导航 | 久久婷婷五月综合97色直播| 国产精品亚洲综合专区片高清久久久 | 久久精品三级视频| 天天爽天天爽天天片a久久网| 久久国产高潮流白浆免费观看| 午夜精品久久久久久中宇| 性欧美大战久久久久久久| Xx性欧美肥妇精品久久久久久 | 国内精品久久久久久久亚洲| 99久久精品毛片免费播放| 久久婷婷激情综合色综合俺也去| 99久久综合国产精品免费| 欧美精品丝袜久久久中文字幕|