{"id":254,"date":"2022-01-11T11:18:50","date_gmt":"2022-01-11T03:18:50","guid":{"rendered":"https:\/\/www.wennroy.com\/?p=254"},"modified":"2022-01-11T11:39:47","modified_gmt":"2022-01-11T03:39:47","slug":"1036-escape-a-large-maze","status":"publish","type":"post","link":"https:\/\/wennroy.com\/index.php\/2022\/01\/11\/1036-escape-a-large-maze\/","title":{"rendered":"1036.\u9003\u79bb\u5927\u8ff7\u5bab"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">\u5728\u4e00\u4e2a $10^6\\times 10^6$ \u7684\u7f51\u683c\u4e2d\uff0c\u6bcf\u4e2a\u7f51\u683c\u4e0a\u65b9\u683c\u7684\u5750\u6807\u4e3a\u00a0<code>(x, y)<\/code>\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u73b0\u5728\u4ece\u6e90\u65b9\u683c\u00a0<code>source = [sx, sy]<\/code>\u00a0\u5f00\u59cb\u51fa\u53d1\uff0c\u610f\u56fe\u8d76\u5f80\u76ee\u6807\u65b9\u683c\u00a0<code>target = [$t_x$, $t_y$]<\/code> \u3002\u6570\u7ec4 <code>blocked<\/code> \u662f\u5c01\u9501\u7684\u65b9\u683c\u5217\u8868\uff0c\u5176\u4e2d\u6bcf\u4e2a <code>blocked[i] = [xi, yi]<\/code> \u8868\u793a\u5750\u6807\u4e3a <code>(xi, yi)<\/code> \u7684\u65b9\u683c\u662f\u7981\u6b62\u901a\u884c\u7684\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u6bcf\u6b21\u79fb\u52a8\uff0c\u90fd\u53ef\u4ee5\u8d70\u5230\u7f51\u683c\u4e2d\u5728\u56db\u4e2a\u65b9\u5411\u4e0a\u76f8\u90bb\u7684\u65b9\u683c\uff0c\u53ea\u8981\u8be5\u65b9\u683c \u4e0d \u5728\u7ed9\u51fa\u7684\u5c01\u9501\u5217\u8868\u00a0<code>blocked<\/code>\u00a0\u4e0a\u3002\u540c\u65f6\uff0c\u4e0d\u5141\u8bb8\u8d70\u51fa\u7f51\u683c\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u53ea\u6709\u5728\u53ef\u4ee5\u901a\u8fc7\u4e00\u7cfb\u5217\u7684\u79fb\u52a8\u4ece\u6e90\u65b9\u683c\u00a0<code>source<\/code> \u5230\u8fbe\u76ee\u6807\u65b9\u683c\u00a0<code>target<\/code> \u65f6\u624d\u8fd4\u56de\u00a0<code>true<\/code>\u3002\u5426\u5219\uff0c\u8fd4\u56de <code>false<\/code>\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u63d0\u793a\uff1a<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>0 &lt;= <code>blocked.length<\/code> &lt;= 200<\/li><li><code>blocked[i].length<\/code> == 2<\/li><li>0 &lt;= <code>xi, yi<\/code> &lt; 106<\/li><li><code>source.length<\/code> == <code>target.length<\/code> == 2<\/li><li>0 &lt;= <code>sx, sy, tx, ty<\/code> &lt; $10^6$<\/li><li><code>source<\/code> != <code>target<\/code><\/li><li>\u9898\u76ee\u6570\u636e\u4fdd\u8bc1 <code>source<\/code> \u548c <code>target<\/code> \u4e0d\u5728\u5c01\u9501\u5217\u8868\u5185<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e00\u9053dfs\u600e\u4e48\u90fd\u4f1a\u8d85\u65f6\u7684\u9898\u76ee\u3002\u6700\u540e\u5f97\u53d6\u5de7\u3002\u7531\u4e8e\u53ea\u6709200\u4e2a<code>blocked<\/code>\uff0c\u6240\u4ee5\u6700\u591a\u53ea\u8981\u7ecf\u8fc720000\u683c\u5c31\u80fd\u786e\u4fdd\u4e00\u5b9a\u80fd\u8d70\u5230\u5916\u9762\u3002\u6700\u540e\u7684\u6781\u7aef\u60c5\u51b5\u89c1\u6700\u540e\u7684\u4f8b\u5b50\u3002<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">class Solution:\n    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n        if blocked == []:\n            return True\n        blocked = set(map(tuple, blocked))\n\n        def dfs(self, x, y, target, state, blocked):\n            if x == target[0] and y == target[1]:\n                return True\n            state.add((x,y))\n            if len(state) > 20000:\n                return True\n            px = [1,0,-1,0]\n            py = [0,1,0,-1]\n            for i in range(4):\n                new_x = x + px[i]\n                new_y = y + py[i]\n                if new_x >= 0 and new_x &lt; 10**6 and new_y >=0 and new_y &lt; 10**6 and not (new_x,new_y) in state and not (new_x,new_y) in blocked:\n                    if dfs(self,new_x,new_y, target, state, blocked):\n                        return True\n            \n            return False\n        \n        return dfs(self, source[0], source[1], target, set(), blocked) and dfs(self, target[0], target[1], source, set(), blocked)<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u6267\u884c\u7528\u65f6\uff1a<\/strong>1032 ms, \u5728\u6240\u6709\u00a0Python3\u00a0\u63d0\u4ea4\u4e2d\u51fb\u8d25\u4e8624.61%\u7684\u7528\u6237<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u5185\u5b58\u6d88\u8017\uff1a<\/strong>48.8 MB, \u5728\u6240\u6709\u00a0Python3\u00a0\u63d0\u4ea4\u4e2d\u51fb\u8d25\u4e866.15%\u7684\u7528\u6237<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u8fd0\u884c\u65f6\u95f4\u4ee5\u53ca\u5185\u5b58\u6d88\u8017\u8f83\u5927\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u6781\u7aef\u4f8b\u5b50\uff1a<\/strong><\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">[[0,199],[1,198],[2,197],[3,196],[4,195],[5,194],[6,193],[7,192],[8,191],[9,190],[10,189],[11,188],[12,187],[13,186],[14,185],[15,184],[16,183],[17,182],[18,181],[19,180],[20,179],[21,178],[22,177],[23,176],[24,175],[25,174],[26,173],[27,172],[28,171],[29,170],[30,169],[31,168],[32,167],[33,166],[34,165],[35,164],[36,163],[37,162],[38,161],[39,160],[40,159],[41,158],[42,157],[43,156],[44,155],[45,154],[46,153],[47,152],[48,151],[49,150],[50,149],[51,148],[52,147],[53,146],[54,145],[55,144],[56,143],[57,142],[58,141],[59,140],[60,139],[61,138],[62,137],[63,136],[64,135],[65,134],[66,133],[67,132],[68,131],[69,130],[70,129],[71,128],[72,127],[73,126],[74,125],[75,124],[76,123],[77,122],[78,121],[79,120],[80,119],[81,118],[82,117],[83,116],[84,115],[85,114],[86,113],[87,112],[88,111],[89,110],[90,109],[91,108],[92,107],[93,106],[94,105],[95,104],[96,103],[97,102],[98,101],[99,100],[100,99],[101,98],[102,97],[103,96],[104,95],[105,94],[106,93],[107,92],[108,91],[109,90],[110,89],[111,88],[112,87],[113,86],[114,85],[115,84],[116,83],[117,82],[118,81],[119,80],[120,79],[121,78],[122,77],[123,76],[124,75],[125,74],[126,73],[127,72],[128,71],[129,70],[130,69],[131,68],[132,67],[133,66],[134,65],[135,64],[136,63],[137,62],[138,61],[139,60],[140,59],[141,58],[142,57],[143,56],[144,55],[145,54],[146,53],[147,52],[148,51],[149,50],[150,49],[151,48],[152,47],[153,46],[154,45],[155,44],[156,43],[157,42],[158,41],[159,40],[160,39],[161,38],[162,37],[163,36],[164,35],[165,34],[166,33],[167,32],[168,31],[169,30],[170,29],[171,28],[172,27],[173,26],[174,25],[175,24],[176,23],[177,22],[178,21],[179,20],[180,19],[181,18],[182,17],[183,16],[184,15],[185,14],[186,13],[187,12],[188,11],[189,10],[190,9],[191,8],[192,7],[193,6],[194,5],[195,4],[196,3],[197,2],[198,1],[199,0]]\n[0,0]\n[200,200]<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u5b98\u65b9\u6807\u7b54\uff1a<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u65b9\u6cd5\u4e00\uff1a\u6709\u9650\u6b65\u6570\u7684\u5e7f\u5ea6\u4f18\u5148<\/strong><\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">class Solution:\n    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n        \"\"\"\n        BLOCKED: \u5728\u5305\u56f4\u5708\u4e2d\n        VALID:   \u4e0d\u5728\u5305\u56f4\u5708\u4e2d\n        FOUND:   \u65e0\u8bba\u5728\u4e0d\u5728\u5305\u56f4\u5708\u4e2d\uff0c\u4f46\u5728 n(n-1)\/2 \u6b65\u641c\u7d22\u7684\u8fc7\u7a0b\u4e2d\u7ecf\u8fc7\u4e86 target\n        \"\"\"\n        BLOCKED, VALID, FOUND = -1, 0, 1\n        BOUNDARY = 10**6\n\n        if len(blocked) &lt; 2:\n            return True\n\n        hash_blocked = set(tuple(pos) for pos in blocked)\n\n        def check(start: List[int], finish: List[int]) -> int:\n            sx, sy = start\n            fx, fy = finish\n            countdown = len(blocked) * (len(blocked) - 1) \/\/ 2\n            \n            q = deque([(sx, sy)])\n            visited = set([(sx, sy)])\n            \n            while q and countdown > 0:\n                x, y = q.popleft()\n                for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n                    if 0 &lt;= nx &lt; BOUNDARY and 0 &lt;= ny &lt; BOUNDARY and (nx, ny) not in hash_blocked and (nx, ny) not in visited:\n                        if (nx, ny) == (fx, fy):\n                            return FOUND\n                        countdown -= 1\n                        q.append((nx, ny))\n                        visited.add((nx, ny))\n            \n            if countdown > 0:\n                return BLOCKED\n            return VALID\n\n        if (result := check(source, target)) == FOUND:\n            return True\n        elif result == BLOCKED:\n            return False\n        else:\n            result = check(target, source)\n            if result == BLOCKED:\n                return False\n            return True<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u65b9\u6cd5\u4e8c\uff1a\u79bb\u6563\u5316 + \u5e7f\u5ea6\u4f18\u5148\u641c\u7d22<\/strong><\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">class Solution:\n    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n        if len(blocked) &lt; 2:\n            return True\n            \n        BOUNDARY = 10**6\n\n        # \u79bb\u6563\u5316\n        rows = sorted(set(pos[0] for pos in blocked) | {source[0], target[0]})\n        columns = sorted(set(pos[1] for pos in blocked) | {source[1], target[1]})\n        r_mapping, c_mapping = dict(), dict()\n        \n\n        r_id = (0 if rows[0] == 0 else 1)\n        r_mapping[rows[0]] = r_id\n        for i in range(1, len(rows)):\n            r_id += (1 if rows[i] == rows[i - 1] + 1 else 2)\n            r_mapping[rows[i]] = r_id\n        if rows[-1] != BOUNDARY - 1:\n            r_id += 1\n\n        c_id = (0 if columns[0] == 0 else 1)\n        c_mapping[columns[0]] = c_id\n        for i in range(1, len(columns)):\n            c_id += (1 if columns[i] == columns[i - 1] + 1 else 2)\n            c_mapping[columns[i]] = c_id\n        if columns[-1] != BOUNDARY - 1:\n            c_id += 1\n\n        grid = [[0] * (c_id + 1) for _ in range(r_id + 1)]\n        for x, y in blocked:\n            grid[r_mapping[x]][c_mapping[y]] = 1\n        \n        sx, sy = r_mapping[source[0]], c_mapping[source[1]]\n        tx, ty = r_mapping[target[0]], c_mapping[target[1]]\n\n        q = deque([(sx, sy)])\n        grid[sx][sy] = 1\n        while q:\n            x, y = q.popleft()\n            for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n                if 0 &lt;= nx &lt;= r_id and 0 &lt;= ny &lt;= c_id and grid[nx][ny] != 1:\n                    if (nx, ny) == (tx, ty):\n                        return True\n                    q.append((nx, ny))\n                    grid[nx][ny] = 1\n        \n        return False<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u53ef\u4ee5\u8bf4\u4e24\u79cd\u65b9\u6cd5\u90fd\u7279\u522b\u5de7\u4e86\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u6765\u6e90\uff1a\u529b\u6263\uff08LeetCode\uff09<br>\u94fe\u63a5\uff1a<a href=\"https:\/\/leetcode-cn.com\/problems\/escape-a-large-maze\">https:\/\/leetcode-cn.com\/problems\/escape-a-large-maze<\/a><br>\u8457\u4f5c\u6743\u5f52\u9886\u6263\u7f51\u7edc\u6240\u6709\u3002\u5546\u4e1a\u8f6c\u8f7d\u8bf7\u8054\u7cfb\u5b98\u65b9\u6388\u6743\uff0c\u975e\u5546\u4e1a\u8f6c\u8f7d\u8bf7\u6ce8\u660e\u51fa\u5904\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u4e00\u4e9b\u5c0f\u77e5\u8bc6\uff1a<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>\u4e8c\u5143list\u8f6cset\u7684\u64cd\u4f5c\u4e00\uff1a<code data-enlighter-language=\"python\" class=\"EnlighterJSRAW\">blocked = set(map(tuple, blocked))<\/code><\/li><li>\u4e8c\u5143list\u8f6cset\u7684\u64cd\u4f5c\u4e8c\uff1a<code data-enlighter-language=\"python\" class=\"EnlighterJSRAW\">blocked = {tuple(p) for p in blocked}<\/code><\/li><li>python 3.8\u66f4\u65b0 \u6d77\u8c61\u8fd0\u7b97\u7b26 := \u89c1 <a href=\"https:\/\/blog.csdn.net\/qq_40244755\/article\/details\/102685199\">Python :=\u6d77\u8c61\u8fd0\u7b97\u7b26\u6700\u7b80\u5355\u7684\u89e3\u91ca<\/a><\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u5728\u4e00\u4e2a $10^6\\times 10^6$ \u7684\u7f51\u683c &hellip;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_import_markdown_pro_load_document_selector":0,"_import_markdown_pro_submit_text_textarea":"","footnotes":""},"categories":[6,22],"tags":[24,23,25,26],"class_list":["post-254","post","type-post","status-publish","format-standard","hentry","category-leetcode","category-findpath_algorithm","tag-bfs","tag-dfs","tag-leetcode","tag-26"],"_links":{"self":[{"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/posts\/254","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/comments?post=254"}],"version-history":[{"count":4,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/posts\/254\/revisions"}],"predecessor-version":[{"id":259,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/posts\/254\/revisions\/259"}],"wp:attachment":[{"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/media?parent=254"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/categories?post=254"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/tags?post=254"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}