{"id":7557,"date":"2020-10-24T23:26:42","date_gmt":"2020-10-25T06:26:42","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7557"},"modified":"2020-10-25T15:30:14","modified_gmt":"2020-10-25T22:30:14","slug":"leetcode-1631-path-with-minimum-effort","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-1631-path-with-minimum-effort\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1631. Path With Minimum Effort"},"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 1631. Path With Minimum Effort - \u5237\u9898\u627e\u5de5\u4f5c EP364\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/bfDOyz0DnQ8?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>You are a hiker preparing for an upcoming hike. You are given&nbsp;<code>heights<\/code>, a 2D array of size&nbsp;<code>rows x columns<\/code>, where&nbsp;<code>heights[row][col]<\/code>&nbsp;represents the height of cell&nbsp;<code>(row, col)<\/code>. You are situated in the top-left cell,&nbsp;<code>(0, 0)<\/code>, and you hope to travel to the bottom-right cell,&nbsp;<code>(rows-1, columns-1)<\/code>&nbsp;(i.e.,&nbsp;<strong>0-indexed<\/strong>). You can move&nbsp;<strong>up<\/strong>,&nbsp;<strong>down<\/strong>,&nbsp;<strong>left<\/strong>, or&nbsp;<strong>right<\/strong>, and you wish to find a route that requires the minimum&nbsp;<strong>effort<\/strong>.<\/p>\n\n\n\n<p>A route&#8217;s&nbsp;<strong>effort<\/strong>&nbsp;is the&nbsp;<strong>maximum absolute difference<\/strong>in heights between two consecutive cells of the route.<\/p>\n\n\n\n<p>Return&nbsp;<em>the minimum&nbsp;<strong>effort<\/strong>&nbsp;required to travel from the top-left cell to the bottom-right cell.<\/em><\/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\/2020\/10\/04\/ex1.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> heights = [[1,2,2],[3,8,2],[5,3,5]]\n<strong>Output:<\/strong> 2\n<strong>Explanation:<\/strong> The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells.\nThis is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/10\/04\/ex2.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> heights = [[1,2,3],[3,8,4],[5,3,5]]\n<strong>Output:<\/strong> 1\n<strong>Explanation:<\/strong> The route of [1,2,3,4,5] has a maximum absolute difference of 1 in consecutive cells, which is better than route [1,3,5,3,5].\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/10\/04\/ex3.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]\n<strong>Output:<\/strong> 0\n<strong>Explanation:<\/strong> This route does not require any effort.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>rows == heights.length<\/code><\/li><li><code>columns == heights[i].length<\/code><\/li><li><code>1 &lt;= rows, columns &lt;= 100<\/code><\/li><li><code>1 &lt;= heights[i][j] &lt;= 10<sup>6<\/sup><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: &#8220;Lazy BFS \/ DP&#8221;<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1631-ep364-1.png\" alt=\"\" class=\"wp-image-7562\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1631-ep364-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1631-ep364-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1631-ep364-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1631-ep364-2.png\" alt=\"\" class=\"wp-image-7563\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1631-ep364-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1631-ep364-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1631-ep364-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>dp[y][x] = min(max(dp[ty][tx], abs(h[ty][tx] &#8211; h[y][x]))) (x, y) and (tx, ty) are neighbors<br>repeat this process for at most rows * cols times.<br>if dp does not change after one round which means we found the optimal solution and can break earlier.<\/p>\n\n\n\n<p>Time complexity: O(n^2*m^2))<br>Space complexity: O(nm)<\/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, 824 ms\nclass Solution {\npublic:\n  int minimumEffortPath(vector<vector<int>>& heights) {\n    const int r = heights.size();\n    const int c = heights[0].size();\n    int dp[100][100];\n    memset(dp, 0x7f, sizeof(dp));\n    dp[0][0] = 0;\n    vector<int> dirs{0, -1, 0, 1, 0};\n    for (int k = 0; k < r * c; ++k) {\n      bool stable = true;\n      for (int y = 0; y < r; ++y)\n        for (int x = 0; x < c; ++x)\n          for (int d = 0; d < 4; ++d) {\n            int tx = x + dirs[d];\n            int ty = y + dirs[d + 1];\n            if (tx < 0 || tx == c || ty < 0 || ty == r) continue;\n            int t = max(dp[ty][tx], abs(heights[ty][tx] - heights[y][x]));\n            if (t < dp[y][x]) {\n              stable = false;\n              dp[y][x] = t;\n            }\n          }    \n      if (stable) break;\n    }\n    return dp[r - 1][c - 1];\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Binary Search + BFS<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1631-ep364-3.png\" alt=\"\" class=\"wp-image-7564\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1631-ep364-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1631-ep364-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1631-ep364-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>Use binary search to guess a cost and then check whether there is path that is under the cost.<\/p>\n\n\n\n<p>Time complexity: O(mn*log(max(h) - min(h)))<br>Space complexity: O(mn)<\/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, 620 ms\nclass Solution {\npublic:\n  int minimumEffortPath(vector<vector<int>>& heights) {\n    const int rows = heights.size();\n    const int cols = heights[0].size();    \n    vector<int> dirs{0, -1, 0, 1, 0};\n    auto bfs = [&](int cost) -> bool {\n      queue<pair<int, int>> q;\n      vector<int> seen(cols * rows);\n      q.emplace(0, 0);\n      seen[0] = 1;\n      while (!q.empty()) {\n        auto [cx, cy] = q.front(); q.pop();\n        if (cx == cols - 1 && cy == rows - 1) return true;\n        for (int i = 0; i < 4; ++i) {\n          int x = cx + dirs[i];\n          int y = cy + dirs[i + 1];\n          if (x < 0 || x == cols || y < 0 || y == rows) continue;\n          if (abs(heights[cy][cx] - heights[y][x]) > cost) continue;\n          if (seen[y * cols + x]++) continue;\n          q.emplace(x, y);\n        }          \n      }\n      return false;\n    };\n    int l = 0, r = 1e6 + 1;\n    while (l < r) {\n      const int m = l + (r - l) \/ 2;\n      if (bfs(m)) {\n        r = m;\n      } else {\n        l = m + 1;\n      }\n    }\n    return l;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 3: Dijkstra<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1631-ep364-4.png\" alt=\"\" class=\"wp-image-7565\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1631-ep364-4.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1631-ep364-4-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1631-ep364-4-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>Time complexity: O(mnlog(mn))<br>Space complexity: O(mn)<\/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, 216 ms\nclass Solution {\npublic:\n  int minimumEffortPath(vector<vector<int>>& heights) {\n    const vector<int> dirs{0, -1, 0, 1, 0}; \n    const int rows = heights.size();\n    const int cols = heights[0].size();\n    using Node = pair<int, int>;\n    priority_queue<Node, vector<Node>, greater<Node>> q;\n    vector<int> dist(rows * cols, INT_MAX \/ 2);    \n    q.emplace(0, 0);\n    dist[0] = 0;\n    while (!q.empty()) {\n      auto [t, u] = q.top(); q.pop();\n      if (u == rows * cols - 1) return t;\n      if (t > dist[u]) continue;\n      const int ux = u % cols;\n      const int uy = u \/ cols;\n      for (int i = 0; i < 4; ++i) {\n        const int x = ux + dirs[i];\n        const int y = uy + dirs[i + 1];\n        if (x < 0 || x == cols || y < 0 || y == rows) continue;\n        const int v = y * cols + x;\n        const int c = abs(heights[uy][ux] - heights[y][x]);\n        if (max(t, c) >= dist[v]) continue;\n        q.emplace(dist[v] = max(t, c), v);\n      }\n    }\n    return -1;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are a hiker preparing for an upcoming hike. You are given&nbsp;heights, a 2D array of size&nbsp;rows x columns, where&nbsp;heights[row][col]&nbsp;represents the height of cell&nbsp;(row, col).&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[76],"tags":[34,18,77,177],"class_list":["post-7557","post","type-post","status-publish","format-standard","hentry","category-graph","tag-bfs","tag-dp","tag-graph","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7557","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=7557"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7557\/revisions"}],"predecessor-version":[{"id":7568,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7557\/revisions\/7568"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7557"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7557"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7557"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}