{"id":6384,"date":"2020-02-29T23:06:28","date_gmt":"2020-03-01T07:06:28","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6384"},"modified":"2020-03-01T13:27:44","modified_gmt":"2020-03-01T21:27:44","slug":"leetcode-1368-minimum-cost-to-make-at-least-one-valid-path-in-a-grid","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-1368-minimum-cost-to-make-at-least-one-valid-path-in-a-grid\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1368. Minimum Cost to Make at Least One Valid Path in a Grid"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1368. Minimum Cost to Make at Least One Valid Path in a Grid - \u5237\u9898\u627e\u5de5\u4f5c EP310\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/ox8Z8maR6R8?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>Given a&nbsp;<em>m<\/em>&nbsp;x&nbsp;<em>n<\/em><code>grid<\/code>. Each cell of the&nbsp;<code>grid<\/code>&nbsp;has a sign pointing to the next cell you should visit if you are currently in this cell. The sign of&nbsp;<code>grid[i][j]<\/code>&nbsp;can be:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><strong>1<\/strong>&nbsp;which means go to the cell to the right. (i.e go from&nbsp;<code>grid[i][j]<\/code>&nbsp;to&nbsp;<code>grid[i][j + 1]<\/code>)<\/li><li><strong>2<\/strong>&nbsp;which means go to the cell to the left. (i.e go from&nbsp;<code>grid[i][j]<\/code>&nbsp;to&nbsp;<code>grid[i][j - 1]<\/code>)<\/li><li><strong>3<\/strong>&nbsp;which means go to the lower cell. (i.e go from&nbsp;<code>grid[i][j]<\/code>&nbsp;to&nbsp;<code>grid[i + 1][j]<\/code>)<\/li><li><strong>4<\/strong>&nbsp;which means go to the upper cell. (i.e go from&nbsp;<code>grid[i][j]<\/code>&nbsp;to&nbsp;<code>grid[i - 1][j]<\/code>)<\/li><\/ul>\n\n\n\n<p>Notice&nbsp;that there could be some&nbsp;<strong>invalid signs<\/strong>&nbsp;on the cells of the&nbsp;<code>grid<\/code>&nbsp;which points outside the&nbsp;<code>grid<\/code>.<\/p>\n\n\n\n<p>You will initially start at the upper left cell&nbsp;<code>(0,0)<\/code>. A valid path in the grid is a path which starts from the upper left&nbsp;cell&nbsp;<code>(0,0)<\/code>&nbsp;and ends at the bottom-right&nbsp;cell&nbsp;<code>(m - 1, n - 1)<\/code>&nbsp;following the signs on the grid. The valid path&nbsp;<strong>doesn&#8217;t have to be the shortest<\/strong>.<\/p>\n\n\n\n<p>You can modify the sign on a cell with&nbsp;<code>cost = 1<\/code>. You can modify the sign on a cell&nbsp;<strong>one time only<\/strong>.<\/p>\n\n\n\n<p>Return&nbsp;<em>the minimum cost<\/em>&nbsp;to make the grid have at least one valid path.<\/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\/02\/13\/grid1.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]\n<strong>Output:<\/strong> 3\n<strong>Explanation:<\/strong> You will start at point (0, 0).\nThe path to (3, 3) is as follows. (0, 0) --&gt; (0, 1) --&gt; (0, 2) --&gt; (0, 3) change the arrow to down with cost = 1 --&gt; (1, 3) --&gt; (1, 2) --&gt; (1, 1) --&gt; (1, 0) change the arrow to down with cost = 1 --&gt; (2, 0) --&gt; (2, 1) --&gt; (2, 2) --&gt; (2, 3) change the arrow to down with cost = 1 --&gt; (3, 3)\nThe total cost = 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\/02\/13\/grid2.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> grid = [[1,1,3],[3,2,2],[1,1,4]]\n<strong>Output:<\/strong> 0\n<strong>Explanation:<\/strong> You can follow the path from (0, 0) to (2, 2).\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\/02\/13\/grid3.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> grid = [[1,2],[4,3]]\n<strong>Output:<\/strong> 1\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 = [[2,2,2],[2,2,2]]\n<strong>Output:<\/strong> 3\n<\/pre>\n\n\n\n<p><strong>Example 5:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> grid = [[4]]\n<strong>Output:<\/strong> 0\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>m == grid.length<\/code><\/li><li><code>n == grid[i].length<\/code><\/li><li><code>1 &lt;= m, n &lt;= 100<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: Lazy BFS (fake DP)<\/strong><\/h2>\n\n\n\n<p>dp[i][j] := min steps to reach (i, j)<\/p>\n\n\n\n<p>Time complexity: O((m+n)*m*n)<br>Space complexity: O(m*n)<\/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\nclass Solution {\npublic:\n  int minCost(vector<vector<int>>& grid) {\n    int m = grid.size();\n    int n = grid[0].size();\n    vector<vector<int>> dp(m, vector<int>(n, INT_MAX \/ 2));    \n        \n    dp[0][0] = 0;\n    auto solve = [&](int x, int y) {\n      int& v = dp[y][x];\n      if (x > 0) v = min(v, dp[y][x - 1] + (grid[y][x - 1] != 1));\n      if (y > 0) v = min(v, dp[y - 1][x] + (grid[y - 1][x] != 3));\n      if (x < n - 1) v = min(v, dp[y][x + 1] + (grid[y][x + 1] != 2));\n      if (y < m - 1) v = min(v, dp[y + 1][x] + (grid[y + 1][x] != 4));\n    };\n    \n    \/\/ At most m + n steps to propagate the results to (m - 1, n -1).\n    for (int k = 0; k <= (m + n); ++k) {\n      for (int y = 0; y < m; ++y)\n        for (int x = 0; x < n; ++x)\n          solve(x, y);\n      for (int y = m - 1; y >= 0; --y)\n        for (int x = n - 1; x >= 0; --x)\n          solve(x, y);\n    }\n    return dp[m - 1][n - 1];\n  }\n};\n<\/pre>\n<\/div><\/div>\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, 88 ms \/ 22.9 MB\nclass Solution {\npublic:\n  int minCost(vector<vector<int>>& grid) {\n    const int m = grid.size();\n    const int n = grid[0].size();\n    vector<vector<int>> dp(m, vector<int>(n, INT_MAX \/ 2));\n    dp[0][0] = 0;\n    while (true) {\n      auto prev(dp);\n      for (int i = 0; i < m; ++i)\n        for (int j = 0; j < n; ++j) {\n          if (i > 0) dp[i][j] = min(dp[i][j], dp[i - 1][j] + (grid[i - 1][j] != 3));\n          if (j > 0) dp[i][j] = min(dp[i][j], dp[i][j - 1] + (grid[i][j - 1] != 1));\n        }            \n      for (int i = m - 1; i >= 0; --i)\n        for (int j = n - 1; j >= 0; --j) {\n          if (i != m - 1) dp[i][j] = min(dp[i][j], dp[i + 1][j] + (grid[i + 1][j] != 4));\n          if (j != n - 1) dp[i][j] = min(dp[i][j], dp[i][j + 1] + (grid[i][j + 1] != 2));\n        }\n      if (prev == dp) break; \/\/ optimal solution obtained.\n    }\n    return dp[m - 1][n - 1];\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: 0-1 BFS<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(m*n)<br>Space complexity: O(m*n)<\/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\nclass Solution {\npublic:\n  int minCost(vector<vector<int>>& grid) {\n    const int m = grid.size();\n    const int n = grid[0].size();\n    deque<pair<int, int>> q{{0, 0}};\n    vector<char> seen(m * n);\n    vector<vector<int>> dirs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};\n    while (!q.empty()) {\n      auto [p, cost] = q.front(); q.pop_front();\n      int x = p % n, y = p \/ n;\n      if (x == n - 1 && y == m - 1) return cost;\n      if (seen[p]++) continue;\n      for (int i = 0; i < 4; ++i) {\n        int tx = x + dirs[i][0], ty = y + dirs[i][1];\n        int tp = ty * n + tx;\n        if (tx < 0 || ty < 0 || tx >= n || ty >= m || seen[tp]) continue;\n        if (grid[y][x] == i + 1)\n          q.emplace_front(tp, cost);\n        else\n          q.emplace_back(tp, cost + 1);\n      }\n    }    \n    return -1;\n  }\n};\n\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given a&nbsp;m&nbsp;x&nbsp;ngrid. Each cell of the&nbsp;grid&nbsp;has a sign pointing to the next cell you should visit if you are currently in this cell. The sign&#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,217,366,42],"class_list":["post-6384","post","type-post","status-publish","format-standard","hentry","category-searching","tag-bfs","tag-hard","tag-omn","tag-search","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6384","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=6384"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6384\/revisions"}],"predecessor-version":[{"id":6388,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6384\/revisions\/6388"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6384"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6384"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6384"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}