{"id":5718,"date":"2019-10-05T21:35:35","date_gmt":"2019-10-06T04:35:35","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5718"},"modified":"2019-10-05T21:36:11","modified_gmt":"2019-10-06T04:36:11","slug":"leetcode-1219-path-with-maximum-gold","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-1219-path-with-maximum-gold\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1219. Path with Maximum Gold"},"content":{"rendered":"\n<p>In a gold mine&nbsp;<code>grid<\/code>&nbsp;of size&nbsp;<code>m * n<\/code>,&nbsp;each cell in this mine has an integer representing the amount of gold&nbsp;in that cell,&nbsp;<code>0<\/code>&nbsp;if it is empty.<\/p>\n\n\n\n<p>Return the maximum amount of gold you&nbsp;can collect under the conditions:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Every time you are located in a cell you will collect all the gold in that cell.<\/li><li>From your position you can walk one step to the left, right, up or down.<\/li><li>You can&#8217;t visit the same cell more than once.<\/li><li>Never visit a cell with&nbsp;<code>0<\/code>&nbsp;gold.<\/li><li>You can start and stop collecting gold from&nbsp;<strong>any&nbsp;<\/strong>position in the grid that has some gold.<\/li><\/ul>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> grid = [[0,6,0],[5,8,7],[0,9,0]]\n<strong>Output:<\/strong> 24\n<strong>Explanation:<\/strong>\n[[0,6,0],\n [5,8,7],\n [0,9,0]]\nPath to get the maximum gold, 9 -&gt; 8 -&gt; 7.\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 = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]\n<strong>Output:<\/strong> 28\n<strong>Explanation:<\/strong>\n[[1,0,7],\n [2,0,6],\n [3,4,5],\n [0,3,0],\n [9,0,20]]\nPath to get the maximum gold, 1 -&gt; 2 -&gt; 3 -&gt; 4 -&gt; 5 -&gt; 6 -&gt; 7.\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,&nbsp;grid[i].length &lt;= 15<\/code><\/li><li><code>0 &lt;= grid[i][j] &lt;= 100<\/code><\/li><li>There are at most&nbsp;<strong>25&nbsp;<\/strong>cells containing gold.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: DFS<\/strong><\/h2>\n\n\n\n<p>Time compleixty: O(4^25) ???<br>Space complexity: O(25)<\/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 getMaximumGold(vector<vector<int>>& g) {\n    int n = g.size();\n    int m = g[0].size();\n    int ans = 0;\n    function<int(int, int)> dfs = [&](int x, int y) {\n      if (x < 0 || x >= m || y < 0 || y >= n || g[y][x] == 0) return 0;\n      int c = 0;\n      swap(c, g[y][x]);\n      int r = c + max({dfs(x - 1, y), dfs(x + 1, y), dfs(x, y - 1), dfs(x, y + 1)});\n      swap(c, g[y][x]);\n      return r;\n    };\n    for (int i = 0; i < n; ++i) \n      for (int j = 0; j < m; ++j)        \n        ans = max(ans, dfs(j, i));\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>In a gold mine&nbsp;grid&nbsp;of size&nbsp;m * n,&nbsp;each cell in this mine has an integer representing the amount of gold&nbsp;in that cell,&nbsp;0&nbsp;if it is empty. Return&#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":[33,278,177],"class_list":["post-5718","post","type-post","status-publish","format-standard","hentry","category-searching","tag-dfs","tag-grid","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5718","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=5718"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5718\/revisions"}],"predecessor-version":[{"id":5720,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5718\/revisions\/5720"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5718"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5718"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5718"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}