什么是在矩阵中找到M个相邻元素的最大总和的最快方法

Question

假设我有一个尺寸为N(N <= 50)的方阵,相邻的元素不包括对角线.

在给定M的情况下,如何找到M个相邻元素之间的最大总和？

例如,将此矩阵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

我试着这样做,但经过一定的维度,它很慢.

#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

_{该答案不包括代码（尚），稍后将通过所描述算法的实现进行扩展}

主要困难在于某些“形状”需要多次处理。考虑一个填充矩形的选择。它可以从任何单元格开始并以多种不同的方式（“递归路径”）遍历以达到相同的选择（显然是相同的计算）。这正是需要解决的问题。

为此，您需要预先计算可为给定M选择的各种形状，然后迭代矩阵并为每个单元格（用作形状的左上角）计算并比较所有形状选择的总和。

预计算是通过使用递归函数来完成的，就像在问题中使用路径中的单元“绘制” (2M-1) ²矩阵一样，从中间开始。在最终条件（选择 M 个单元格）中，生成的形状将与累积的“形状列表”中的现有形状进行比较，并且仅在其尚不存在时才添加。 需要解决“+”形状的情况。

应在预计算阶段使用优化，以避免对于非常大的M将问题从计算“转移”到预计算阶段，例如，限制遍历，使得超出起始行是非法的（因此，形状矩阵只需为M(2M-1)大）。