求前缀和暴力枚举幻方边长
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;
}
};