• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode1219.黄金矿工|PathwithMaximumGold

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(let_us_code)
➤博主域名:https://www.zengqiang.org
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

In a gold mine grid of size m * n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty.

Return the maximum amount of gold you can collect under the conditions:

  • Every time you are located in a cell you will collect all the gold in that cell.
  • From your position you can walk one step to the left, right, up or down.
  • You can't visit the same cell more than once.
  • Never visit a cell with 0 gold.
  • You can start and stop collecting gold from any position in the grid that has some gold.

 

Example 1:

Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
 [5,8,7],
 [0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.

Example 2:

Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
Output: 28
Explanation:
[[1,0,7],
 [2,0,6],
 [3,4,5],
 [0,3,0],
 [9,0,20]]
Path to get the maximum gold, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.

 

Constraints:

  • 1 <= grid.length, grid[i].length <= 15
  • 0 <= grid[i][j] <= 100
  • There are at most 25 cells containing gold.

你要开发一座金矿,地质勘测学家已经探明了这座金矿中的资源分布,并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量;如果该单元格是空的,那么就是 0

为了使收益最大化,矿工需要按以下规则来开采黄金:

  • 每当矿工进入一个单元,就会收集该单元格中的所有黄金。
  • 矿工每次可以从当前位置向上下左右四个方向走。
  • 每个单元格只能被开采(进入)一次。
  • 不得开采(进入)黄金数目为 0 的单元格。
  • 矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。

 

示例 1:

输入:grid = [[0,6,0],[5,8,7],[0,9,0]]
输出:24
解释:
[[0,6,0],
 [5,8,7],
 [0,9,0]]
一种收集最多黄金的路线是:9 -> 8 -> 7。

示例 2:

输入:grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
输出:28
解释:
[[1,0,7],
 [2,0,6],
 [3,4,5],
 [0,3,0],
 [9,0,20]]
一种收集最多黄金的路线是:1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7。

 

提示:

  • 1 <= grid.length, grid[i].length <= 15
  • 0 <= grid[i][j] <= 100
  • 最多 25 个单元格中有黄金。

Runtime: 60 ms
Memory Usage: 21.1 MB
 1 class Solution {
 2     let dir:[[Int]] = [[-1,0],[0,-1],[0,1],[1,0]]
 3     func getMaximumGold(_ grid: [[Int]]) -> Int {
 4         let m:Int = grid.count
 5         let n:Int = grid[0].count
 6         var res:Int = 0
 7         for i in 0..<m
 8         {
 9             for j in 0..<n
10             {
11                 if grid[i][j] == 0 {continue}
12                 let num:Int = countneighbor(grid,i,j)
13                 if !((i==0&&j==0)||(i==m-1&&j==0)||(i==m-1&&j==n-1)||(i==0&&j==n-1))&&num>1 {continue}
14                 var seen:[[Bool]] = [[Bool]](repeating: [Bool](repeating: false, count: n), count: m)
15                 let cur:Int = dfs(grid,i,j,&seen)
16                 res = max(cur,res)
17             }
18         }
19         return res
20     }
21     
22     func dfs(_ grid: [[Int]],_ i:Int,_ j:Int,_ seen:inout [[Bool]]) -> Int
23     {
24         let m:Int = grid.count
25         let n:Int = grid[0].count
26         if i>=m||i<0||j>=n||j<0||seen[i][j]||grid[i][j] == 0 {return 0}
27         seen[i][j] = true
28         let l:Int = dfs(grid,i-1,j,&seen)
29         let r:Int = dfs(grid,i+1,j,&seen)
30         let u:Int = dfs(grid,i,j - 1,&seen)
31         let d:Int = dfs(grid,i,j + 1,&seen)
32         seen[i][j] = false
33         return grid[i][j] + max(l,max(r,max(u,d)))
34     }
35     
36     func countneighbor(_ grid: [[Int]],_ i:Int,_ j:Int) -> Int
37     {
38         var count:Int = 0
39         let m:Int = grid.count
40         let n:Int = grid[0].count
41         for d in dir
42         {
43             let x:Int = d[0]+i
44             let y:Int = d[1]+j
45             if x>=0 && x<m && y>=0 && y<n && grid[x][y] != 0
46             {
47                 count += 1
48             }
49         }
50         return count
51     }
52 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
swift中UITableView的简单使用发布时间:2022-07-13
下一篇:
Swift中的关键字详解发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap