{"id":3033,"date":"2018-07-08T21:01:49","date_gmt":"2018-07-09T04:01:49","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=3033"},"modified":"2018-09-13T07:54:42","modified_gmt":"2018-09-13T14:54:42","slug":"leetcode-864-shortest-path-to-get-all-keys","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-864-shortest-path-to-get-all-keys\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 864. Shortest Path to Get All Keys"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 864. Shortest Path to Get All Keys - \u5237\u9898\u627e\u5de5\u4f5c EP205\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/A-8ziQc_4pk?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<h1>Problem<\/h1>\n<p>We are given a 2-dimensional\u00a0<code>grid<\/code>.\u00a0<code>\".\"<\/code>\u00a0is an empty cell,\u00a0<code>\"#\"<\/code>\u00a0is\u00a0a wall,\u00a0<code>\"@\"<\/code>\u00a0is the starting point, (<code>\"a\"<\/code>,\u00a0<code>\"b\"<\/code>, &#8230;) are keys, and (<code>\"A\"<\/code>,\u00a0<code>\"B\"<\/code>, &#8230;) are locks.<\/p>\n<p>We start at the starting point, and one move consists of walking one space in one of the 4 cardinal directions.\u00a0 We cannot walk outside the grid, or walk into a wall.\u00a0 If we walk over a key, we pick it up.\u00a0 We can&#8217;t walk over a lock unless we have the corresponding key.<\/p>\n<p>For some\u00a0<span style=\"font-family: monospace;\">1 &lt;= K &lt;= 6<\/span>, there is exactly one lowercase and one uppercase letter of the first\u00a0<code>K<\/code>\u00a0letters of the English alphabet in the grid.\u00a0 This means that there is exactly one key for each lock, and one lock for each key; and also that the letters used to represent the keys and locks were\u00a0chosen in the same order as the English alphabet.<\/p>\n<p>Return the lowest number of moves to acquire all keys.\u00a0 If\u00a0it&#8217;s impossible, return\u00a0<code>-1<\/code>.<\/p>\n<p><strong>Example 1:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong><span id=\"example-input-1-1\">[\"@.a.#\",\"###.#\",\"b.A.B\"]<\/span>\r\n<strong>Output: <\/strong><span id=\"example-output-1\">8<\/span>\r\n<\/pre>\n<p><strong>Example 2:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong><span id=\"example-input-2-1\">[\"@..aA\",\"..B#.\",\"....b\"]<\/span>\r\n<strong>Output: <\/strong><span id=\"example-output-2\">6<\/span>\r\n<\/pre>\n<p><strong>Note:<\/strong><\/p>\n<ol>\n<li><code>1 &lt;= grid.length\u00a0&lt;= 30<\/code><\/li>\n<li><code>1 &lt;= grid[0].length\u00a0&lt;= 30<\/code><\/li>\n<li><code>grid[i][j]<\/code>\u00a0contains only<code>\u00a0'.'<\/code>,\u00a0<code>'#'<\/code>,\u00a0<code>'@'<\/code>,\u00a0<code>'a'-<\/code><code>'f<\/code><code>'<\/code>\u00a0and\u00a0<code>'A'-'F'<\/code><\/li>\n<li>The number of keys is in\u00a0<code>[1, 6]<\/code>.\u00a0 Each key has a different letter and opens exactly one lock.<\/li>\n<\/ol>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-3042\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/865-ep205-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/865-ep205-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/865-ep205-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/865-ep205-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<h1><strong>Solution: BFS<\/strong><\/h1>\n<p>Time complexity: O(m*n*64)<\/p>\n<p>Space complexity: O(m*n*64)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 8 ms\r\nclass Solution {\r\npublic:\r\n  int shortestPathAllKeys(vector&lt;string&gt;&amp; grid) {\r\n    int m = grid.size();\r\n    int n = grid[0].size();    \r\n    int all_keys = 0;\r\n    queue&lt;int&gt; q;\r\n    vector&lt;vector&lt;vector&lt;int&gt;&gt;&gt; seen(m, vector&lt;vector&lt;int&gt;&gt;(n, vector&lt;int&gt;(64, 0)));\r\n        \r\n    \/\/ Init\r\n    for (int i = 0; i &lt; m; ++i)\r\n      for (int j = 0; j &lt; n; ++j) {\r\n        const char c = grid[i][j];\r\n        if (c == '@') {\r\n          q.push((j &lt;&lt; 16) | (i &lt;&lt; 8));\r\n          seen[i][j][0] = 1;\r\n        } else if (c &gt;= 'a' &amp;&amp; c &lt;= 'f') {\r\n          all_keys |= (1 &lt;&lt; (c - 'a'));\r\n        }\r\n      }\r\n    \r\n    const vector&lt;int&gt; dirs{-1, 0, 1, 0, -1};\r\n    \r\n    int steps = 0;\r\n    while (!q.empty()) {\r\n      int size = q.size();\r\n      while (size--) {\r\n        int s = q.front(); q.pop();\r\n        int x = s &gt;&gt; 16;\r\n        int y = (s &gt;&gt; 8) &amp; 0xFF;\r\n        int keys = s &amp; 0xFF;        \r\n        if (keys == all_keys) return steps;\r\n        for (int i = 0; i &lt; 4; ++i) {\r\n          int nkeys = keys;\r\n          int nx = x + dirs[i];\r\n          int ny = y + dirs[i + 1];          \r\n          if (nx &lt; 0 || nx &gt;= n || ny &lt; 0 || ny &gt;= m) continue;\r\n          const char c = grid[ny][nx];          \r\n          if (c == '#') continue; \/\/ Wall\r\n          \/\/ Do not have the key.\r\n          if (c &gt;= 'A' &amp;&amp; c &lt;= 'F' &amp;&amp; !(keys &amp; (1 &lt;&lt; (c - 'A')))) continue;\r\n          \/\/ Update the keys we have.\r\n          if (c &gt;= 'a' &amp;&amp; c &lt;= 'f') nkeys |= (1 &lt;&lt; (c - 'a'));\r\n          if (seen[ny][nx][nkeys]) continue;\r\n          q.push((nx &lt;&lt; 16) | (ny &lt;&lt; 8) | nkeys);\r\n          seen[ny][nx][nkeys] = 1;\r\n        }\r\n      }\r\n      ++steps;\r\n    }\r\n    return -1;\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:python decode:true \"># Author: Huahua, 390 ms\r\nclass Solution:\r\n  def shortestPathAllKeys(self, grid):\r\n    m, n = len(grid), len(grid[0])\r\n    all_keys = 0\r\n    seen = [[[None]* 64 for _ in range(n)] for _ in range(m)]\r\n    q = collections.deque()\r\n    for i in range(m):\r\n      for j in range(n):\r\n        c = grid[i][j]\r\n        if c == '@':\r\n          q.append((j &lt;&lt; 16) | (i &lt;&lt; 8))\r\n          seen[i][j][0] = 1\r\n        elif c &gt;= 'a' and c &lt;= 'f':\r\n          all_keys |= (1 &lt;&lt; (ord(c) - ord('a')))\r\n          \r\n    dirs = [-1, 0, 1, 0, -1]\r\n    steps = 0\r\n    while q:\r\n      size = len(q)\r\n      while size &gt; 0:\r\n        size -= 1\r\n        s = q.popleft()\r\n        x = s &gt;&gt; 16\r\n        y = (s &gt;&gt; 8) &amp; 0xff\r\n        keys = s &amp; 0xff        \r\n        if keys == all_keys: return steps\r\n        for i in range(4):\r\n          nx, ny, nkeys = x + dirs[i], y + dirs[i + 1], keys          \r\n          if nx &lt; 0 or nx &gt;= n or ny &lt; 0 or ny &gt;= m: continue\r\n          c = grid[ny][nx]\r\n          if c == '#': continue\r\n          if c in string.ascii_uppercase and keys &amp; (1 &lt;&lt; (ord(c) - ord('A'))) == 0: continue\r\n          if c in string.ascii_lowercase: nkeys |= (1 &lt;&lt; (ord(c) - ord('a')))\r\n          if seen[ny][nx][nkeys]: continue\r\n          q.append((nx &lt;&lt; 16) | (ny &lt;&lt; 8) | nkeys)\r\n          seen[ny][nx][nkeys] = 1\r\n      steps += 1\r\n    return -1<\/pre>\n<\/div><\/div>\n<h1><strong>Related Problems<\/strong><\/h1>\n<ul>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-847-shortest-path-visiting-all-nodes\/\">\u82b1\u82b1\u9171 LeetCode 847. Shortest Path Visiting All Nodes<\/a><\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem We are given a 2-dimensional\u00a0grid.\u00a0&#8220;.&#8221;\u00a0is an empty cell,\u00a0&#8220;#&#8221;\u00a0is\u00a0a wall,\u00a0&#8220;@&#8221;\u00a0is the starting point, (&#8220;a&#8221;,\u00a0&#8220;b&#8221;, &#8230;) are keys, and (&#8220;A&#8221;,\u00a0&#8220;B&#8221;, &#8230;) are locks. We start at&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[278,82,87],"class_list":["post-3033","post","type-post","status-publish","format-standard","hentry","category-searching","tag-grid","tag-hashtable","tag-shortest-path","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3033","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=3033"}],"version-history":[{"count":9,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3033\/revisions"}],"predecessor-version":[{"id":3946,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3033\/revisions\/3946"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3033"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3033"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3033"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}