力扣1895.最大的幻方

力扣1895.最大的幻方

• 求前缀和暴力枚举幻方边长

  • 求行列前缀和

•   class Solution {
    public:
        int largestMagicSquare(vector<vector<int>>& grid) {
            int n = grid.size() , m = grid[0].size();
            vector<vector<int>> rowsum(n,vector<int>(m));
            for(int i=0;i<n;i++)
            {
                rowsum[i][0] = grid[i][0];
                for(int j=1;j<m;j++)
                    rowsum[i][j] = rowsum[i][j-1] + grid[i][j];
            }
    
            vector<vector<int>> colsum(n,vector<int>(m));
            for(int j=0;j<m;j++)
            {
                colsum[0][j] = grid[0][j];
                for(int i=1;i<n;i++)
                    colsum[i][j] = colsum[i-1][j] + grid[i][j];
            }
    		//倒序枚举边长
            for(int edge = min(m,n) ; edge>=2;edge--)
            {
                for(int i=0;i <= n - edge;i++)
                {
                    for(int j=0;j<=m - edge;j++)
                    {
                        //求模板 以第一行的和为例
                        int stdsum = rowsum[i][j + edge - 1] - (j ? rowsum[i][j-1] : 0);
                        bool check = true;
    
                        for(int ii = i + 1;ii < i + edge; ii ++)
                        {
                            if(rowsum[ii][j + edge - 1] - (j ? rowsum[ii][j - 1] : 0 ) != stdsum)
                            {
                                check = false;
                                break;
                            }
    
                            if(!check) continue;
    
                            for(int jj=j;jj<edge + j;jj++)
                            {
                                if(colsum[i + edge - 1][jj] - (i ? colsum[i-1][jj] :0) != stdsum)
                                {
                                    check = false;
                                    break;
                                }
                            }
    
                            if(!check) continue;
    
                            int d1 = 0,d2 = 0;
                            for(int k=0;k<edge;k++)
                            {
                                d1 += grid[i+k][j+k];
                                d2 += grid[i+k][j+edge-1-k];
                            }
                            if(d1 == stdsum && d2 == stdsum)
                                return edge;
                        }
                    }
                }
            }
            return 1;
        }
    };