Bir matrisin k bağlı öğelerinin maksimum toplamı

Question

Pozitif tamsayı değerleri ve K tam sayılı bir ızgara verildi. Bağlı elemanların maksimum toplamı K nedir? İşte

bana bu sorunu tanımlamak için yardımcı olabilir 6.

Birisi bir K değere sahip bir 5x5 matris bir örnektir? Bunu nasıl çözmeye başlayabilirim?
Bildiğim tek yol, bu matrisin her hücresi için önce bir arama yapmaktır. Ama bence bu en iyi yaklaşım değil.

Yinelenen hücrelere izin verilmez. Burada Bağlı

hücre yatay veya dikey

Answer 1

gitmene olarak memoizing, sen etrafında Menderes herhalde diğer komşu olan sadece anlamına gelir. Memolanmış yolları temsil etmek için ayna görüntüsü bitsetlerini kullandım, böylece oluşturuldukları herhangi bir yönden anında tanınabilirlerdi. İşte Python bir versiyonu (hash uzunluğu boyutları altıya itibaren yolları için sayıları içerir):

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) 

Çıktı:

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

GÜNCELLEME: Bu soru, Whats the fastest way to find biggest sum of M adjacent elements in a matrix buna benzer ve ben Şekillerimin orta bölümlerinden uzanan oluşumları içerme önerimde bir revizyon yapılması gerektiğini fark ettim. İşte düzeltilmiş kodum, şekilleri hash etmek için setler kullanıyor. Bana göre bir DFS yığınının büyüklüğünü O(m) (arama alanı hala büyük olmasına rağmen) olarak tutması gerekiyor.

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) 

Çıktı: Ben bu soruyu Buraya ait emin değilim

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