{"id":5881,"date":"2019-11-26T22:18:21","date_gmt":"2019-11-27T06:18:21","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5881"},"modified":"2019-11-28T09:57:45","modified_gmt":"2019-11-28T17:57:45","slug":"leetcode-1263-minimum-moves-to-move-a-box-to-their-target-location","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-1263-minimum-moves-to-move-a-box-to-their-target-location\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1263. Minimum Moves to Move a Box to Their Target Location"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1263. Minimum Moves to Move a Box to Their Target Location - \u5237\u9898\u627e\u5de5\u4f5c EP279\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/LtJgcasp5J8?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>\n<\/div><\/figure>\n\n\n\n<p>Storekeeper is a&nbsp;game&nbsp;in which the player pushes boxes around in a warehouse&nbsp;trying to get them to target locations.<\/p>\n\n\n\n<p>The game is represented by a&nbsp;<code>grid<\/code>&nbsp;of size&nbsp;<code>n*<\/code><code>m<\/code>, where each element is a wall, floor, or a box.<\/p>\n\n\n\n<p>Your task is move the box&nbsp;<code>'B'<\/code>&nbsp;to the target position&nbsp;<code>'T'<\/code>&nbsp;under the following rules:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Player is represented by character&nbsp;<code>'S'<\/code>&nbsp;and&nbsp;can move up, down, left, right in the&nbsp;<code>grid<\/code>&nbsp;if it is a floor (empy cell).<\/li><li>Floor is represented by character&nbsp;<code>'.'<\/code>&nbsp;that means free cell to walk.<\/li><li>Wall is represented by character&nbsp;<code>'#'<\/code>&nbsp;that means obstacle&nbsp;&nbsp;(impossible to walk there).&nbsp;<\/li><li>There is only one box&nbsp;<code>'B'<\/code>&nbsp;and one&nbsp;target cell&nbsp;<code>'T'<\/code>&nbsp;in the&nbsp;<code>grid<\/code>.<\/li><li>The box can be moved to an adjacent free cell by standing next to the box and then moving in the direction of the box. This is a&nbsp;<strong>push<\/strong>.<\/li><li>The player cannot walk through the box.<\/li><\/ul>\n\n\n\n<p>Return the minimum number of&nbsp;<strong>pushes<\/strong>&nbsp;to move the box to the target. If there is no way to reach the target, return&nbsp;<code>-1<\/code>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/11\/06\/sample_1_1620.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> grid = [[\"#\",\"#\",\"#\",\"#\",\"#\",\"#\"],\n               [\"#\",\"T\",\"#\",\"#\",\"#\",\"#\"],\n&nbsp;              [\"#\",\".\",\".\",\"B\",\".\",\"#\"],\n&nbsp;              [\"#\",\".\",\"#\",\"#\",\".\",\"#\"],\n&nbsp;              [\"#\",\".\",\".\",\".\",\"S\",\"#\"],\n&nbsp;              [\"#\",\"#\",\"#\",\"#\",\"#\",\"#\"]]\n<strong>Output:<\/strong> 3\n<strong>Explanation: <\/strong>We return only the number of times the box is pushed.<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> grid = [[\"#\",\"#\",\"#\",\"#\",\"#\",\"#\"],\n               [\"#\",\"T\",\"#\",\"#\",\"#\",\"#\"],\n&nbsp;              [\"#\",\".\",\".\",\"B\",\".\",\"#\"],\n&nbsp;              [\"#\",\"#\",\"#\",\"#\",\".\",\"#\"],\n&nbsp;              [\"#\",\".\",\".\",\".\",\"S\",\"#\"],\n&nbsp;              [\"#\",\"#\",\"#\",\"#\",\"#\",\"#\"]]\n<strong>Output:<\/strong> -1\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> grid = [[\"#\",\"#\",\"#\",\"#\",\"#\",\"#\"],\n&nbsp;              [\"#\",\"T\",\".\",\".\",\"#\",\"#\"],\n&nbsp;              [\"#\",\".\",\"#\",\"B\",\".\",\"#\"],\n&nbsp;              [\"#\",\".\",\".\",\".\",\".\",\"#\"],\n&nbsp;              [\"#\",\".\",\".\",\".\",\"S\",\"#\"],\n&nbsp;              [\"#\",\"#\",\"#\",\"#\",\"#\",\"#\"]]\n<strong>Output:<\/strong> 5\n<strong>Explanation:<\/strong>  push the box down, left, left, up and up.\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> grid = [[\"#\",\"#\",\"#\",\"#\",\"#\",\"#\",\"#\"],\n&nbsp;              [\"#\",\"S\",\"#\",\".\",\"B\",\"T\",\"#\"],\n&nbsp;              [\"#\",\"#\",\"#\",\"#\",\"#\",\"#\",\"#\"]]\n<strong>Output:<\/strong> -1\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= grid.length &lt;= 20<\/code><\/li><li><code>1 &lt;= grid[i].length &lt;= 20<\/code><\/li><li><code>grid<\/code>&nbsp;contains only characters&nbsp;<code>'.'<\/code>,&nbsp;<code>'#'<\/code>,&nbsp;&nbsp;<code>'S'<\/code>&nbsp;,&nbsp;<code>'T'<\/code>,&nbsp;or&nbsp;<code>'B'<\/code>.<\/li><li>There is only one character&nbsp;<code>'S'<\/code>,&nbsp;<code>'B'<\/code>&nbsp;and&nbsp;<code>'T'<\/code>&nbsp;in the&nbsp;<code>grid<\/code>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: BFS + DFS<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/11\/1263-ep279.png\" alt=\"\" class=\"wp-image-5886\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/11\/1263-ep279.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/11\/1263-ep279-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/11\/1263-ep279-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>BFS to search by push steps to find miminal number of pushes. Each time we move from the previous position (initial position or last push position) to a new push position. Use DFS to check that whether that path exist or not.<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nstruct Node {\n  int bx;\n  int by;\n  int px;\n  int py;\n\n  int key() const { return ((by * 20 + bx) << 16) | (py * 20 + px); }\n};\n\nclass Solution {\n public:\n  int minPushBox(vector<vector<char>>& grid) {\n    const int n = grid.size();\n    const int m = grid[0].size();\n    Node start;\n    Node end;\n\n    for (int y = 0; y < n; ++y)\n      for (int x = 0; x < m; ++x)\n        if (grid[y][x] == 'B') {\n          start.bx = x;\n          start.by = y;\n        } else if (grid[y][x] == 'S') {\n          start.px = x;\n          start.py = y;\n        } else if (grid[y][x] == 'T') {\n          end.bx = x;\n          end.by = y;\n        }\n\n    auto hasPath = [&#038;](const Node&#038; cur, int tx, int ty) {\n      vector<int> seen(m*n);\n      function<bool(int, int)> dfs = [&](int x, int y) {\n        if (x < 0 || x >= m || y < 0 || y >= n || grid[y][x] == '#')\n          return false;\n        if (x == cur.bx && y == cur.by) return false;\n        int key = y * m + x;\n        if (seen[key]) return false;\n        seen[key] = 1;\n        if (x == tx && y == ty) return true;\n        return dfs(x + 1, y) || dfs(x - 1, y) || dfs(x, y + 1) || dfs(x, y - 1);\n      };\n\n      return dfs(cur.px, cur.py);\n    };\n\n    auto canPush = [&](const Node& cur, int dx, int dy, Node* nxt) {\n      const int bx = cur.bx + dx;\n      const int by = cur.by + dy;\n      if (bx < 0 || bx >= m || by < 0 || by >= n || grid[by][bx] == '#')\n        return false;\n      if (!hasPath(cur, cur.bx - dx, cur.by - dy)) return false;\n      nxt->bx = bx;\n      nxt->by = by;\n      nxt->px = cur.bx;\n      nxt->py = cur.by;\n      return true;\n    };\n\n    const vector<int> dirs{0, -1, 0, 1, 0};\n    unordered_set<int> seen;\n    queue<Node> q;\n    q.push(start);\n    int steps = 0;\n\n    while (q.size()) {\n      int size = q.size();\n      while (size--) {\n        Node cur = q.front();\n        q.pop();\n        for (int i = 0; i < 4; ++i) {\n          Node nxt;\n          if (!canPush(cur, dirs[i], dirs[i + 1], &#038;nxt) ||\n              seen.count(nxt.key()))\n            continue;\n          if (nxt.bx == end.bx &#038;&#038; nxt.by == end.by) return steps + 1;\n          seen.insert(nxt.key());\n          q.push(nxt);\n        }\n      }\n      ++steps;\n    }\n    return -1;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: A* + BFS<\/strong><\/h2>\n\n\n\n<p>g : history = # of pushes<br>h: heuristics = Manhattan distance from the current box position to the target position, always &lt;= actual moves.<br>f = g + h<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua, 4 ms, 17.5 MB\nstruct Node {\n  int bx;\n  int by;\n  int px;\n  int py;\n  int h;\n  int g;\n\n  int key() const {\n    return ((by * m + bx) << 2) | ((bx - px) + 1) | ((by - py) + 1) >> 1;\n  }\n  int f() const { return g + h; }\n  bool operator< (const Node&#038; o) const {\n    return f() > o.f();\n  }\n  \n  static int m;\n};\n\nint Node::m;\n\nclass Solution {\n public:\n  int minPushBox(vector<vector<char>>& grid) {\n    const vector<int> dirs{0, -1, 0, 1, 0};\n    const int n = grid.size();\n    const int m = Node::m = grid[0].size();\n    Node start;\n    Node end;\n\n    for (int y = 0; y < n; ++y)\n      for (int x = 0; x < m; ++x)\n        if (grid[y][x] == 'B') {\n          start.bx = x;\n          start.by = y;\n        } else if (grid[y][x] == 'S') {\n          start.px = x;\n          start.py = y;\n        } else if (grid[y][x] == 'T') {\n          end.bx = x;\n          end.by = y;\n        }\n    \n    auto isValid = [&#038;](int x, int y) {\n      return !(x < 0 || x >= m || y < 0 || y >= n || grid[y][x] == '#');\n    };\n\n    auto hasPath = [&](const Node& cur, int tx, int ty) {\n      if (!isValid(tx, ty)) return false;\n      vector<int> seen(m*n);\n      queue<int> q;\n      q.push(cur.py * m + cur.px);\n      seen[cur.py * m + cur.px] = 1;\n      while (q.size()) {\n        int x = q.front() % m;\n        int y = q.front() \/ m;\n        q.pop();\n        for (int i = 0; i < 4; ++i) {\n          int nx = x + dirs[i];\n          int ny = y + dirs[i + 1];\n          if (!isValid(nx, ny)) continue;\n          if (nx == cur.bx &#038;&#038; ny == cur.by) continue;\n          if (nx == tx &#038;&#038; ny == ty) return true;\n          if (seen[ny * m  + nx]++) continue;          \n          q.push(ny * m + nx);\n        }\n      }\n      return false;\n    };\n\n    auto canPush = [&#038;](const Node&#038; cur, int dx, int dy, Node* nxt) {\n      nxt->bx = cur.bx + dx;\n      nxt->by = cur.by + dy;\n      nxt->px = cur.bx;\n      nxt->py = cur.by;\n      nxt->g = cur.g + 1;\n      nxt->h = abs(nxt->bx - end.bx) + abs(nxt->by - end.by);\n      if (!isValid(nxt->bx, nxt->by)) return false;\n      return hasPath(cur, cur.bx - dx, cur.by - dy);\n    };\n\n    vector<int> seen(m*n*4);\n    priority_queue<Node> q;\n    start.g = 0;\n    start.h = abs(start.bx - end.bx) + abs(start.by - end.by);\n    q.push(start);\n    \n    while (q.size()) {   \n      Node cur = q.top();\n      q.pop();\n      for (int i = 0; i < 4; ++i) {\n        Node nxt;\n        if (!canPush(cur, dirs[i], dirs[i + 1], &#038;nxt) || seen[nxt.key()]++) continue;        \n        if (nxt.bx == end.bx &#038;&#038; nxt.by == end.by) return nxt.g;        \n        q.push(nxt);\n      }\n    }\n    return -1;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Storekeeper is a&nbsp;game&nbsp;in which the player pushes boxes around in a warehouse&nbsp;trying to get them to target locations. The game is represented by a&nbsp;grid&nbsp;of size&nbsp;n*m,&#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":[34,33,217,42],"class_list":["post-5881","post","type-post","status-publish","format-standard","hentry","category-searching","tag-bfs","tag-dfs","tag-hard","tag-search","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5881","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=5881"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5881\/revisions"}],"predecessor-version":[{"id":5889,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5881\/revisions\/5889"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5881"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5881"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5881"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}