行列のk個の接続要素の最大合計

Question

正の整数値と整数のグリッドが与えられた場合K。 Kの要素の最大合計は何ですか？ここで

は、5×5の行列の一例である6

のK値で誰かがこの問題を識別するために私を助けることができますか？どのように私はそれを解決し始めることができますか？
私が知っている唯一の方法は、この行列の各セルの深度最初の検索を行うことです。しかし、私はこれが最善の方法ではないと思います。

反復する細胞は使用できません。ここに接続され

セルが水平または垂直に

Answer 1

他に隣接しているだけであることを意味私はあなたが行くようにmemoizing、周りの蛇行可能性があるとします。私は、彼らが構築されたどの方向からも即座に認識できるように、メモのついたパスを表すために鏡像ビットセットを使用しました。ここでは、Pythonでのバージョンがあります（ハッシュの長さはサイズ六から一からのパスの数を含みます）：

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 
""" 

UPDATE：この質問は、Whats the fastest way to find biggest sum of M adjacent elements in a matrixこの1と同様であり、I私の提案では、形状の中間部分から延びる構造を含むように修正が必要であることを認識しました。ここで私の改訂コードは、シェイプをハッシュするセットを使用しています。 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 
"""