力扣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;}};