内容简介:翻译自:https://stackoverflow.com/questions/32824002/maximum-sum-of-k-connected-elements-of-a-matrix
给定具有正整数值和整数K的网格.K连通元素的最大总和是多少?
以下是K值为6的5×5矩阵的示例.
有人可以帮我识别这个问题吗?我该如何开始解决它?
我知道的唯一方法是对该矩阵的每个单元格进行深度优先搜索.但我认为这不是最好的方法.
不允许重复细胞.
Connected here means only that a cell is adjacent to the other horizontally or vertically
我想你可以蜿蜒前行,随时随地记忆.我使用镜像位集来表示记忆路径,这样它们就可以从构造的任何方向立即识别出来.这是 Python 中的一个版本(哈希长度包括从1到6的路径的计数):
from sets import Set def f(a,k): stack = [] hash = Set([]) best = (0,0) # sum, path n = len(a) for y in range(n): for x in range(n): stack.append((1 << (n * y + x),y,x,a[y][x],1)) while len(stack) > 0: (path,y,x,s,l) = stack.pop() if l == k and path not in hash: hash.add(path) if s > best[0]: best = (s,path) elif path not in hash: hash.add(path) if y < n - 1: stack.append((path | (1 << (n * (y + 1) + x)),y + 1,x,s + a[y + 1][x],l + 1)) if y > 0: stack.append((path | (1 << (n * (y - 1) + x)),y - 1,x,s + a[y - 1][x],l + 1)) if x < n - 1: stack.append((path | (1 << (n * y + x + 1)),y,x + 1,s + a[y][x + 1],l + 1)) if x > 0: stack.append((path | (1 << (n * y + x - 1)),y,x - 1,s + a[y][x - 1],l + 1)) print best print len(hash)
输出:
arr = [[31,12,7,1,14] ,[23,98,3,87,1] ,[5,31,8,2,99] ,[12,3,42,17,88] ,[120,2,7,5,7]] f(arr,6) """ (377, 549312) sum, path 1042 hash length 549312 = 00000 01110 11000 10000 """
更新:这个问题类似于这个问题, Whats the fastest way to find biggest sum of M adjacent elements in a matrix ,我意识到我的建议需要修改,以包括从形状的中间部分延伸的构造.这是我修改后的代码,使用集合来散列形状.在我看来,DFS应该保持堆栈大小为O(m)的顺序(尽管搜索空间仍然很大).
from sets import Set def f(a,m): stack = [] hash = Set([]) best = (0,[]) # sum, shape n = len(a) for y in range(n): for x in range(n): stack.append((a[y][x],Set([(y,x)]),1)) while len(stack) > 0: s,shape,l = stack.pop() key = str(sorted(list(shape))) if l == m and key not in hash: hash.add(key) if s > best[0]: best = (s,shape) elif key not in hash: hash.add(key) for (y,x) in shape: if y < n - 1 and (y + 1,x) not in shape: copy = Set(shape) copy.add((y + 1,x)) stack.append((s + a[y + 1][x],copy,l + 1)) if y > 0 and (y - 1,x) not in shape: copy = Set(shape) copy.add((y - 1,x)) stack.append((s + a[y - 1][x],copy,l + 1)) if x < n - 1 and (y,x + 1) not in shape: copy = Set(shape) copy.add((y,x + 1)) stack.append((s + a[y][x + 1],copy,l + 1)) if x > 0 and (y,x - 1) not in shape: copy = Set(shape) copy.add((y,x - 1)) stack.append((s + a[y][x - 1],copy,l + 1)) print best print len(hash)
输出:
arr = [[31,12,7,1,14] ,[23,98,3,87,1] ,[5,31,8,2,99] ,[12,3,42,17,88] ,[120,2,7,5,7]] f(arr,6) """ (377, Set([(1, 2), (1, 3), (1, 1), (2, 3), (3, 4), (2, 4)])) 2394 hash length """
翻译自:https://stackoverflow.com/questions/32824002/maximum-sum-of-k-connected-elements-of-a-matrix
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 关于 Dubbo 连通性的一些思考
- NOIP专题复习3 图论-强连通分量
- iOS可视化动态绘制连通图(Swift版)
- Linkis 数据中间件,打造全面连通融合的金融级大数据平台
- 挖洞经验 | 利用Jira的邮件服务器连通测试功能发现其CSRF漏洞
- 机器学习 | SVD矩阵分解算法,对矩阵做拆分,然后呢?
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
UNIX编程艺术
[美] Eric S. Raymond / 姜宏、何源、蔡晓骏 / 电子工业出版社 / 2012-8 / 99.00元
《UNIX编程艺术》主要介绍了Unix系统领域中的设计和开发哲学、思想文化体系、原则与经验,由公认的Unix编程大师、开源运动领袖人物之一Eric S.Raymond倾力多年写作而成。包括Unix设计者在内的多位领域专家也为《UNIX编程艺术》贡献了宝贵的内容。《UNIX编程艺术》内容涉及社群文化、软件开发设计与实现,覆盖面广、内容深邃,完全展现了作者极其深厚的经验积累和领域智慧。一起来看看 《UNIX编程艺术》 这本书的介绍吧!