给定一个具有正整数和整数k的网格，k连通元素的最大和是多少？
下面是一个k值为6的5x5矩阵的示例。
有人能帮我找出这个问题吗？我怎样才能开始解决呢？
我知道的唯一方法是对这个矩阵的每个单元进行深度优先搜索。但我认为这不是最好的方法。
不允许重复单元格。
此处连接仅表示一个单元格水平或垂直与另一个相邻
最佳答案
我想你可以边走边记。我使用镜像位集来表示记忆的路径，这样它们就可以从构建的任何方向立即识别出来。下面是python中的一个版本（hash长度包括从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
"""