当前位置:网站首页>Simulation volume leetcode [general] 1219 Golden Miner
Simulation volume leetcode [general] 1219 Golden Miner
2022-07-06 06:18:00 【Encounter simulation volume】
Summary : Simulation volume Leetcode Summary of questions
1219. Golden Miner
You're going to develop a gold mine , Geological surveyors have found out the distribution of resources in this gold mine , And use the size of m * n The grid of grid It's marked . An integer in each cell represents the amount of gold in that cell ; If the cell is empty , So that is 0.
To maximize revenue , Miners need to mine gold according to the following rules :
Every time a miner enters a unit , All the gold in that cell is collected .
Miners can walk up, down, left and right from their current position every time .
Each cell can only be mined ( Get into ) once .
No mining ( Get into ) The number of gold is 0 Cells of .
Miners can get out of the grid Any one Cells with gold start or stop .
Example 1:
Input :grid = [[0,6,0],[5,8,7],[0,9,0]]
Output :24
explain :
[[0,6,0],
[5,8,7],
[0,9,0]]
One way to collect the most gold is :9 -> 8 -> 7.
Example 2:
Input :grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
Output :28
explain :
[[1,0,7],
[2,0,6],
[3,4,5],
[0,3,0],
[9,0,20]]
One way to collect the most gold is :1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.
Tips :
1 <= grid.length, grid[i].length <= 15
0 <= grid[i][j] <= 100
most 25 There's gold in one cell .
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/path-with-maximum-gold
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Code :
from leetcode_python.utils import *
class Solution:
def __init__(self):
self.res = 0
@lru_cache(None)
def next(self,rowid,colid):
res = []
for i, j in ((rowid - 1, colid), (rowid, colid - 1), (rowid + 1, colid), (rowid, colid + 1)):
if 0 <= i < self.height and 0 <= j < self.width:
res.append([i, j])
return res
def dfs(self,r,c,now):
g = self.grid[r][c]
now+=g
self.res = max(self.res,now)
self.grid[r][c]=0
for nextr,nextc in self.next(r,c):
if self.grid[nextr][nextc]:
self.dfs(nextr,nextc,now)
self.grid[r][c]=g
def getMaximumGold(self, grid: List[List[int]]) -> int:
self.grid = grid
self.height,self.width = len(grid), len(grid[0])
for i in range(self.height):
for j in range(self.width):
if grid[i][j]:
self.dfs(i,j,0)
return self.res
def test(data_test):
s = Solution()
data = data_test # normal
# data = [list2node(data_test[0])] # list turn node
return s.getMaximumGold(*data)
def test_obj(data_test):
result = [None]
obj = Solution(*data_test[1][0])
for fun, data in zip(data_test[0][1::], data_test[1][1::]):
if data:
res = obj.__getattribute__(fun)(*data)
else:
res = obj.__getattribute__(fun)()
result.append(res)
return result
if __name__ == '__main__':
datas = [
[
[[0,6,0],[5,8,7],[0,9,0]]],
]
for data_test in datas:
t0 = time.time()
print('-' * 50)
print('input:', data_test)
print('output:', test(data_test))
print(f'use time:{
time.time() - t0}s')
remarks :
GitHub:https://github.com/monijuan/leetcode_python
CSDN Summary : Simulation volume Leetcode Summary of questions
You can add QQ Group communication :1092754609
leetcode_python.utils See the description on the summary page for details
First brush questions , Then generated by script blog, If there is any mistake, please leave a message , I see it will be revised ! thank you !
边栏推荐
猜你喜欢
F - true liars (category and search set +dp)
Pat (Grade B) 2022 summer exam
VINS-Mono: A Robust and Versatile Monocular Visual-Inertial State Estimator
keil MDK中删除添加到watch1中的变量
GTSAM中李群的运用
Buuctf-[gxyctf2019] no dolls (xiaoyute detailed explanation)
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Manhattan distance sum - print diamond
P问题、NP问题、NPC问题、NP-hard问题详解
数据库-当前读与快照读
随机推荐
【API接口工具】postman-界面使用介绍
Overview of three core areas of Mathematics: algebra
「 WEB测试工程师 」岗位一面总结
Eigen稀疏矩阵操作
【Postman】Collections配置运行过程
Detailed explanation of P problem, NP problem, NPC problem and NP hard problem
联合索引的左匹配原则
Nodejs realizes the third-party login of Weibo
Buuctf-[bjdctf2020]zjctf, but so (xiaoyute detailed explanation)
[postman] the monitors monitoring API can run periodically
Overview of three core areas of Mathematics: geometry
GTSAM中ISAM2和IncrementalFixedLagSmoother说明
JMeter做接口测试,如何提取登录Cookie
leetcode 24. 两两交换链表中的节点
Coordinatorlayout+nestedscrollview+recyclerview pull up the bottom display is incomplete
D - How Many Answers Are Wrong
Database isolation level
Still worrying about how to write web automation test cases? Senior test engineers teach you selenium test case writing hand in hand
Hypothesis testing learning notes
JDBC Requset 对应内容及功能介绍