力扣1895.最大的幻方

admin2024-07-05  42

力扣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;
          }
      };
    
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!