Whats the fastest way to find biggest sum of M adjacent elements in a matrix [duplicate]

Question

Suppose I have a square matrix of dimension N (N <= 50) and the adjacent elements do not include the diagonals.

How can I find the biggest sum between M adjacent elements, given M?

For example, take this matrix 4x4:

Matrix:           For M = 3           For M = 4

3 1 5 2           3  1  5  2          3  1  5 2
2 6 1 3           2 [6] 1  3          2 [6] 1 3
1 4 4 2           1 [4][4] 2          1 [4] 4 2
5 3 2 7           5  3  2  7         [5][3] 2 7

                  Biggest = 14        Biggest = 18

I tried to do this way, but after a certain dimension, it is very slow.

#include <bits/stdc++.h>

using namespace std;

int mat[51][51];
int mark[51][51];
int m, n;
int biggest;

void search(int row, int column, int sum, int steps){
    if(row < 0 || row >= n || column < 0 || column >= n || mark[row][column]) {
        return;
    }

    sum += mat[row][column];

    mark[row][column] = 1;

    if(steps == m){

        if(biggest < sum) biggest = sum;

    }

    else{

        search(row - 1, column, sum, steps+1);
        search(row + 1, column, sum, steps+1);
        search(row, column + 1, sum, steps+1);
        search(row, column - 1, sum, steps+1);
    }

    mark[row][column] = 0;
}


int main(){

    memset(mat, 0, sizeof(mat));
    memset(mark, 0, sizeof(mark));

    biggest = 0;
    scanf("%d", &n);
    scanf("%d", &m);

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            scanf("%d", &mat[i][j]);
        }
    }


    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            search(i, j, 0, 1);
        }
    }


    printf("%d", biggest);
    return 0;

}

Answer 1

_{This answer does not include code (yet) and will later be extended with an implementation of the described algorithm}

The main difficulty is that certain "shapes" are processed many times. Consider a selection that is a filled rectangle. It can start from any cell and traverse in multiple different ways ("recursive paths") to reach the same selection (and obviously the same calculation). It is this issue that needs to be tackled.

To do that, you need to precompute the various shapes that can be selected for the given M, then iterate the matrix and for each cell (serving as the top-left of the shape) calculate and compare the sum for all shape selections.

The precomputation is done by using a recursive function just like in the question that "paints" a (2M-1)² matrix with the cells in the path, starting in the middle. In the end condition (M cells selected), the generated shape is compared to existing shapes in the accumulating "shapes list", and only added if it's not already there. need to solve for "+" shape scenario.

Optimizations should be used in the precompute stage to avoid " transferring" the problem from the computation to the precomputation stage for very large Ms, for example, limit traversals such that it is illegal to go above the starting row (and as a result, the shape matrix only needs to be M(2M-1) big).

Answer 2

Here's an elementary depth-first-search in Python, using sets to hash the shapes (it's a revision of my answer here, Maximum sum of k connected elements of a matrix). 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:

matrix = [[3, 1, 5, 2,]           
         ,[2, 6, 1, 3,]        
         ,[1, 4, 4, 2]
         ,[5, 3, 2, 7]]

f(matrix,4) 
"""
(18, Set([(3, 1), (3, 0), (2, 1), (1, 1)]))
205 hash length
"""