+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2019-08(47)

2019-09(90)

2019-10(13)

2019-11(9)

2019-12(19)

力扣——黄金矿工

发布于2020-08-01 18:15     阅读(88)     评论(0)     点赞(8)     收藏(1)


你要开发一座金矿,地质勘测学家已经探明了这座金矿中的资源分布,并用大小为 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 个单元格中有黄金。

题意:
1.金矿不为0的才可以进入
2.金矿不能重复进入

思路:
1.找到哪些点可以是起点
2.遍历每个起点的所有路径,找出最大值

解决:
起点(边界点和左下角点):
1.起点必须不为零;
2.并且为了减少不必要执行,应该将一条路径的子路省去,这就要求我们把边界点(有零个或一个非零相邻金矿的点)当作起点
3.同时考虑当路径是回路时,没有边界点,所以只把左下角的点(有两个相邻节点,并且上边,右边有金矿)当起点。(当然,右下,左上,左下角都行)
3.有3,4个非零相邻金矿的点为起点,必定不会是最大值(你可以试试)

回溯找最大值:
1.终点:当上下左右不含非零点时为终点,此时比较并记录现最大值。
2.遍历路线:当发现某一个临点非零,便进入。为了防止发生回路,进入前需要将此点值变为零即可。遍历后恢复其原值,一边其他起点遍历。

class Solution:
    def getMaximumGold(self, grid: List[List[int]]) -> int:
    #当该点非零,并且为边界点或左下角点时返回Ture
        def begin(i,j):
            if grid[i][j]:#黄金值非零是起点的第一个条件
                num=0
                for p,q in zip([i-1,i+1,i,i],[j,j,j-1,j+1]):#记录他又几个相邻非零节点
                    if 0<=p<m and 0<=q<n and grid[p][q]:
                        num+=1
                if num<=1:#一个或0个,是边界点,可以当起点
                    return True
                if num==2 and 0<=i-1<m and j+1<n and grid[i-1][j] and grid[i][j+1]:#两个并且在上边和右边是左下角点,可以当起点
                    return True
            return False#值为零,或有3,4非零相邻节点不是起点
       #遍历每个起点的所有路径 
        def dg(i,j,max_now):
            over=True #True,说明相邻点都没有黄金,终点
            for p,q in zip([i-1,i+1,i,i],[j,j,j-1,j+1]):#观察上下左右
                if 0<=p<m and 0<=q<n and grid[p][q]:#相邻点存在,且有黄金吗?
                    grid_old=grid[p][q]#挖相邻点黄金值
                    grid[p][q]=0#相邻点黄金为0
                    dg(p,q,max_now+grid_old)#增加金值,并进入此相邻点
                    grid[p][q]=grid_old#相邻点探索完毕,恢复其原始值,一边下一起点探索
                    over=False#False,说明相邻点有黄金,非终点
            if over:#此点是终点吗
                self.max=max(self.max,max_now)#比较原最大值,记录最大
        #行列,最大值
        m=len(grid)
        n=len(grid[0])
        self.max=0
        #遍历所有点,如果是起点则遍历所有路径
        for i in range(m):
            for j in range(n):
                if begin(i,j):#是起点吗?
                    grid_old=grid[i][j]#挖起点黄金值
                    grid[i][j]=0#起点黄金为零
                    dg(i,j,grid_old)#以起点开始,增加金值,进入起点
                    grid[i][j]=grid_old#相邻点探索完毕,恢复其原始值,一边下一起点探索
        return self.max#返回最大值

相关:
zip() 函数用于将可迭代的对象作为参数,将对象中对应的元素打包成一个个元组,然后返回由这些元组组成的列表。
例:

>>>a = [1,2,3]
>>> b = [4,5,6]
>>> c = [4,5,6,7,8]
>>> zipped = zip(a,b)     # 打包为元组的列表
[(1, 4), (2, 5), (3, 6)]
>>> zip(a,c)              # 元素个数与最短的列表一致
[(1, 4), (2, 5), (3, 6)]
>>> zip(*zipped)          # 与 zip 相反,*zipped 可理解为解压,返回二维矩阵式
[(1, 2, 3), (4, 5, 6)]

原文链接:https://blog.csdn.net/honglouyibeng/article/details/107718466



所属网站分类: 技术文章 > 博客

作者:dfh8374

链接: https://www.pythonheidong.com/blog/article/468754/

来源: python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

8 0
收藏该文
已收藏

评论内容:(最多支持255个字符)