矩阵的 k 个连通元素的最大和 [英] Maximum sum of k connected elements of a matrix
问题描述
给定一个具有正整数值和整数 K 的网格.K 个连通元素的最大和是多少?
Given a grid with positive integer values and an integer K. What is the maximum sum of K connected elements ?
以下是 K 值为 6 的 5x5 矩阵示例.
Here is a example of a 5x5 matrix with a K value of 6.
有人可以帮我找出这个问题吗?我该如何开始解决它?
我知道的唯一方法是对该矩阵的每个单元格进行深度优先搜索.但我认为这不是最好的方法.
Someone can help me to identify this problem? how can i start to solve it ?
The only way i know is to do a depth first search for each cell of this matrix. But i think that this is not the best approach.
不允许重复单元格.
此处连接仅表示一个单元格在水平或垂直方向上与另一个单元格相邻
Connected here means only that a cell is adjacent to the other horizontally or vertically
推荐答案
我想你可以四处闲逛，边走边记.我使用镜像位集来表示记忆路径，以便从它们构建的任何方向都可以立即识别它们.这是 Python 中的一个版本(哈希长度包括大小为 1 到 6 的路径计数):
I suppose you could meander around, memoizing as you go. I used mirror-image bitsets to represent the memoized paths so that they would be instantly recognizable from any direction they get constructed. Here's a version in Python (the hash length includes counts for paths from sizes one to six):
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
"""
更新:这个问题类似于这个，找到矩阵中 M 个相邻元素的最大和的最快方法是什么，我意识到我的建议需要修改以包括从中间部分延伸的结构形状.这是我修改后的代码，使用集合来散列形状.在我看来，DFS 应该将堆栈大小保持在 O(m) 的顺序(尽管搜索空间仍然很大).
UPDATE: This question is similar to this one, Whats the fastest way to find biggest sum of M adjacent elements in a matrix, and I realized that a revision is needed in my suggestion to include formations extending from middle sections of the shapes. Here's my revised code, using sets to hash the shapes. It seems to me that a DFS ought to keep the stack size on the order of O(m) (although the search space is still huge).
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
"""
这篇关于矩阵的 k 个连通元素的最大和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
