矩阵的k个连通元素的最大总和 [英] Maximum sum of k connected elements of a matrix
问题描述
以下是带有 K 的5x5矩阵的示例值为6.
有人可以帮助我识别此问题？我怎么才能开始解决它？
我知道的唯一方法是先深入搜索这个矩阵的每个单元格。但我认为这不是最好的方法。
不允许重复单元。
这里的连接只意味着一个单元格与另一个单元格水平或垂直相邻
<我想你可以迂回曲折，随着记事的进行。我使用镜像位集来表示记忆路径，以便从构建的任何方向即时识别它们。这是Python中的一个版本（哈希长度包括从1到6的路径数）：
$ b
from sets import set
def f（a，k）：
stack = [] $ b $ hash = Set（[]）
best =（0,0 ）＃sum，path
n = len（a）
对于范围（n）中的y：
对于范围（n）中的x：
stack.append（ （1 <<（n * y + x），y，x，a [y] [x]，1））
while len（stack）> 0：
（path，y，x，s，l）= stack.pop（）
如果l == k且路径不在哈希中：
hash.add（路径）
如果s>最佳[0]：
best =（s，path）
elif path不在哈希中：
hash.add（path）
if y< （路径|（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] 1 + 1））
如果x < （路径|（1 <<（n * y + x + 1）），y，x + 1，s + a [y] [x + 1]， 1 + 1））
if x> 0：
stack.append（（路径|（1 <<（n * y + x-1）），y，x-1，s + a [y] [x-1] 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） b $ b 1042散列长度
549312 = 00000
01110
11000
10000
更新：此问题与此类似， O（m）的顺序（尽管搜索空间仍然很大）。
from sets import Set
def f（a，m）：
stack = []
hash = Set（[]）
best =（0，[]）＃sum，shape
n = len（a）
for y in范围（n）：
在范围（n）中为x：
stack.append（（a [y] [x]，Set（[（y，x）]），1））
，而len（堆叠）> 0：
s，shape，l = stack.pop（）
key = str（sorted（list（shape）））
if l == m and密钥不在哈希中：
hash.add（key）
if s>最好[0]：
best =（s，shape）
elif不在哈希中：
hash.add（key）
for（y，x）in shape：
如果y < （（y + 1，x））
stack.append（（（x + 1，x））形式：
copy = Set（shape）
copy.add s + a [y + 1] [x]，copy，l + 1））
if y> 0和（y-1，x）不在形状中：
copy = Set（shape）
copy.add（（y - 1，x））
stack.append（（s + a [y - 1] [x]，copy，l + 1））
if x < （（y，x + 1））：
copy = Set（shape）
copy.add（（y，x + 1））
stack.append（（ s + a [y] [x + 1]，copy，l + 1））
if x> 0和（y，x-1）不在形状中：
copy = Set（形状）
copy.add（（y，x - 1））
stack.append（（s + a [y] [x-1]，copy，l + 1））
print best
print len（hash）
$ b 输出：
$ b
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散列长度
Given a grid with positive integer values and an integer K. What is the maximum sum of K connected elements ?
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.
Repeating cells are not allowed.
Connected here means only that a cell is adjacent to the other horizontally or vertically
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)
Output:
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
"""
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)
Output:
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屋！
