[Swift]LeetCode1219.黄金矿工|PathwithMaximumGold

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [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 }