[Swift]LeetCode1219. 黄金矿工 | Path with Maximum Gold
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（let_us_code）
➤博主域名：https://www.zengqiang.org
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
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
0gold. - 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 <= 150 <= 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 <= 150 <= 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 }