{"id":5601,"date":"2019-09-29T00:58:00","date_gmt":"2019-09-29T07:58:00","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5601"},"modified":"2019-09-29T01:43:18","modified_gmt":"2019-09-29T08:43:18","slug":"leetcode-1210-minimum-moves-to-reach-target-with-rotations","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-1210-minimum-moves-to-reach-target-with-rotations\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1210. Minimum Moves to Reach Target with Rotations"},"content":{"rendered":"\n<p>In an&nbsp;<code>n*n<\/code>&nbsp;grid, there is a snake that spans 2 cells and starts moving from the top left corner at&nbsp;<code>(0, 0)<\/code>&nbsp;and&nbsp;<code>(0, 1)<\/code>. The grid has empty cells represented by zeros and blocked cells represented by ones. The snake wants to reach the lower right corner at&nbsp;<code>(n-1, n-2)<\/code>&nbsp;and&nbsp;<code>(n-1, n-1)<\/code>.<\/p>\n\n\n\n<p>In one move the snake can:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Move one cell to the right&nbsp;if there are no blocked cells there. This move keeps the horizontal\/vertical position of the snake as it is.<\/li><li>Move down one cell&nbsp;if there are no blocked cells there. This move keeps the horizontal\/vertical position of the snake as it is.<\/li><li>Rotate clockwise if it&#8217;s in a horizontal position and the two cells under it are both empty. In that case the snake moves from&nbsp;<code>(r, c)<\/code>&nbsp;and&nbsp;<code>(r, c+1)<\/code>&nbsp;to&nbsp;<code>(r, c)<\/code>&nbsp;and&nbsp;<code>(r+1, c)<\/code>.<br><\/li><li>Rotate counterclockwise&nbsp;if it&#8217;s in a vertical position and the two cells to its right are both empty. In that case the snake moves from&nbsp;<code>(r, c)<\/code>&nbsp;and&nbsp;<code>(r+1, c)<\/code>&nbsp;to&nbsp;<code>(r, c)<\/code>&nbsp;and&nbsp;<code>(r, c+1)<\/code>.<br><\/li><\/ul>\n\n\n\n<p>Return the minimum number of moves to reach the target.<\/p>\n\n\n\n<p>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\/09\/24\/image.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> grid = [[0,0,0,0,0,1],\n               [1,1,0,0,1,0],\n&nbsp;              [0,0,0,0,1,1],\n&nbsp;              [0,0,1,0,1,0],\n&nbsp;              [0,1,1,0,0,0],\n&nbsp;              [0,1,1,0,0,0]]\n<strong>Output:<\/strong> 11\n<strong>Explanation:\n<\/strong>One possible solution is [right, right, rotate clockwise, right, down, down, down, down, rotate counterclockwise, right, down].\n<\/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 = [[0,0,1,1,1,1],\n&nbsp;              [0,0,0,0,1,1],\n&nbsp;              [1,1,0,0,0,1],\n&nbsp;              [1,1,1,0,0,1],\n&nbsp;              [1,1,1,0,0,1],\n&nbsp;              [1,1,1,0,0,0]]\n<strong>Output:<\/strong> 9\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>2 &lt;= n &lt;= 100<\/code><\/li><li><code>0 &lt;= grid[i][j] &lt;= 1<\/code><\/li><li>It is guaranteed that the snake starts at empty cells.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution1: BFS<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(n^2)<br>Space complexity: O(n^2)<\/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, 48 ms, 18.1 MB\nclass Solution {\npublic:\n  inline int pos(int x, int y) {\n    return y * 100 + x;\n  }\n  \n  inline int encode(int p1, int p2) {\n    return (p1 << 16) | p2;\n  }\n  \n  int minimumMoves(vector<vector<int>>& grid) {    \n    int n = grid.size();\n    queue<pair<int, int>> q;\n    unordered_set<int> seen;\n    q.push({pos(0, 0), pos(1, 0)}); \/\/ tail, head\n    seen.insert(encode(pos(0, 0), pos(1, 0)));\n    int steps = 0;\n    auto valid = [&](int x, int y) {\n      bool v = x >= 0 && x < n &#038;&#038; y >= 0 && y < n &#038;&#038; !grid[y][x];      \n      return v;\n    };\n    while (!q.empty()) {\n      int size = q.size();\n      while (size--) {\n        auto p = q.front(); q.pop();\n        int y0 = p.first \/ 100;\n        int x0 = p.first % 100;\n        int y1 = p.second \/ 100;\n        int x1 = p.second % 100;\n                        \n        if (x0 == n - 2 &#038;&#038; y0 == n - 1 &#038;&#038;\n            x1 == n - 1 &#038;&#038; y1 == n - 1) {\n          return steps;\n        }\n        \n        bool h = y0 == y1;        \n        \n        for (int i = 0; i < 3; ++i) {\n          int tx0 = x0;\n          int ty0 = y0;\n          int tx1 = x1;\n          int ty1 = y1;\n          int rx = x0;\n          int ry = y0;\n          switch (i) {\n            case 0: \/\/ down              \n              ++ty0;\n              ++ty1;\n              break;\n            case 1: \/\/ right\n              ++tx0;\n              ++tx1;\n              break;\n            case 2: \/\/ rotate              \n              ++rx;\n              ++ry;\n              if (h) { \/\/ clockwise \n                --tx1;\n                ++ty1;\n              } else { \/\/ counterclockwise  \n                ++tx1;\n                --ty1;\n              }\n              break;\n          }                    \n          if (!valid(tx0, ty0) || !valid(tx1, ty1) || !valid(rx, ry)) continue;          \n          int key = encode(pos(tx0, ty0), pos(tx1, ty1));\n          if (seen.count(key)) continue;\n          seen.insert(key);\n          q.push({pos(tx0, ty0), pos(tx1, ty1)});\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 2: DP<\/strong><\/h2>\n\n\n\n<p>dp[i][j].first = min steps to reach i,j (tail pos) facing right<br>dp[i][j].second = min steps to reach i, j (tail pos) facing down<br>ans = dp[n][n-1].first<\/p>\n\n\n\n<p>Time complexity: O(n^2)<br>Space complexity: O(n^2)<\/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, 16 ms, 12.1MB\nclass Solution {\npublic:\n  int minimumMoves(vector<vector<int>>& grid) {\n    constexpr int kInf = 1e9;\n    const int n = grid.size();\n    vector<vector<pair<int, int>>> dp(n + 1, \n                                      vector<pair<int, int>>(n + 1, {kInf, kInf}));\n    dp[0][1].first = dp[1][0].first = -1;\n    for (int i = 1; i <= n; ++i)\n      for (int j = 1; j <= n; ++j) {\n        bool h = false;\n        bool v = false;\n        if (!grid[i - 1][j - 1] &#038;&#038; j < n &#038;&#038; !grid[i - 1][j]) {\n          dp[i][j].first = min(dp[i - 1][j].first, dp[i][j - 1].first) + 1;\n          h = true;          \n        }\n        if (!grid[i - 1][j - 1] &#038;&#038; i < n &#038;&#038; !grid[i][j - 1]) {\n          dp[i][j].second = min(dp[i - 1][j].second, dp[i][j - 1].second) + 1;\n          v = true;          \n        }\n        if (v &#038;&#038; j < n &#038;&#038; !grid[i][j])\n            dp[i][j].second = min(dp[i][j].second, dp[i][j].first + 1);\n        if (h &#038;&#038; i < n &#038;&#038; !grid[i][j])\n            dp[i][j].first = min(dp[i][j].first, dp[i][j].second + 1);        \n      }      \n    return dp[n][n - 1].first >= kInf ? -1 : dp[n][n - 1].first;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>In an&nbsp;n*n&nbsp;grid, there is a snake that spans 2 cells and starts moving from the top left corner at&nbsp;(0, 0)&nbsp;and&nbsp;(0, 1). The grid has empty&#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,18,217,498],"class_list":["post-5601","post","type-post","status-publish","format-standard","hentry","category-searching","tag-bfs","tag-dp","tag-hard","tag-on2","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5601","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=5601"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5601\/revisions"}],"predecessor-version":[{"id":5606,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5601\/revisions\/5606"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5601"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5601"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5601"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}