找到最大的幻方

Question

给定一个 m x n 整数网格，return 可以在该网格中找到的最大魔方的大小（即边长 k）。

题目可以在leetcode上找到here

我首先想看看一个简单的暴力方法是否会通过，所以我想出了下面的算法

遍历 k 的所有值（从 min(rows,cols) of the matrix 到 1）
对于每个 k 值，通过检查所有可能的子矩阵和 return k 如果可能的话。这将是 O(rows*cols*k^2)

这样会使整体复杂度 O(k^3*rows*cols)。（如有错误请指正）

我在下面附上了我的 C++ 代码

class Solution {
public:
    int largestMagicSquare(vector<vector<int>>& grid) {
        int rows = grid.size(),cols = grid[0].size();
        for(int k = min(rows,cols); k >= 2; k--){ // iterate over all values of k
            for(int i = 0; i < rows-k+1; i++){
                for(int j = 0; j < cols-k+1; j++){
                    
                    int startX = i, startY = j, endX = i+k-1, endY = j+k-1;
                    int diagSum = 0, antiDiagSum = 0;
                    bool valid = true;
                    
                    // calculate sum of diag
                    for(int count = 0; count < k; count++){
                        diagSum += grid[startX][startY];
                        startX++,startY++;
                    }
                    // this is the sum that must be same across all rows, cols, diag and antidiag
                    int sum = diagSum; 
                    
                    // calculate sum of antidiag
                    for(int count = 0; count < k; count++){
                        antiDiagSum += grid[endX][endY];
                        endX--,endY--;
                    }
                    if(antiDiagSum != sum) continue;
                    
                    // calculate sum across cols
                    for(int r = i; r <=i+k-1; r++){
                        int colSum = 0;
                        for(int c = j; c <= j+k-1; c++){
                            colSum += grid[r][c];
                        }
                        if(colSum != sum){
                            valid = false;
                            break;
                        }
                    }
                    if(!valid) continue;
                    
                    // calculate sum across rows
                    for(int c = j; c <= j+k-1; c++){
                        int rowSum = 0;
                        for(int r = i; r <= i+k-1; r++){
                            rowSum += grid[r][c];
                        }
                        if(rowSum != sum){
                            valid = false;
                            break;
                        }
                    }
                    if(!valid) continue;
                    return k;
                }
            }
        }
        return 1;
    }
};

我想我会在解决方案可行后对其进行优化（也许对 k 的值进行二进制搜索）。但是，在通过 Leetcode 上的 74/80 个测试用例后，我的代码对于维度 50x50 矩阵的非常大的测试用例失败了。

我试图找出可能导致它失败的根源，但我不确定错误在哪里。

如有任何帮助，我们将不胜感激。谢谢！
如果需要进一步说明代码，请告诉我

Answer 1

antiDiagSum的计算是错误的：它实际上将与diagSum在同一对角线上的值相加，只是顺序相反。要遍历相反的对角线，您需要增加 Y 坐标并减少 X 坐标（反之亦然），但您的代码会同时减少它们。

通过在同一个循环中计算两个对角线和来解决这个问题可能是最简单的：

for(int count = 0; count < k; count++){
    diagSum += grid[startX][startY];
    antiDiagSum += grid[endX][startY]; 
    startX++, startY++, endX--;
}

找到最大的幻方

Find the largest Magic Square

c++

algorithm

matrix

data-structures

magic-square