leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1895.cpp (1394B)

      1 class Solution {
      2   public:
      3     int largestMagicSquare(const vector<vector<int>> &grid) const {
      4         static int row[51][51] = {}, col[51][51] = {};
      5         const int n = size(grid), m = size(grid[0]);
      6 
      7         for (int i = 0; i < n; i++) {
      8             for (int j = 0; j < m; j++)
      9                 row[i + 1][j + 1] = row[i + 1][j] + grid[i][j];
     10         }
     11 
     12         for (int j = 0; j < m; j++) {
     13             for (int i = 0; i < n; i++)
     14                 col[i + 1][j + 1] = col[i][j + 1] + grid[i][j];
     15         }
     16 
     17         for (int k = min(n, m); k > 1; k--) {
     18             for (int i = k; i <= n; i++) {
     19                 for (int j = k; j <= m; j++) {
     20                     const int r = row[i][j] - row[i][j - k];
     21                     const int c = col[i][j] - col[i - k][j];
     22                     int d1 = 0, d2 = 0;
     23 
     24                     if (r != c) goto nothing;
     25                     for (int l = 0; l < k; l++) {
     26                         if (r != row[i - l][j] - row[i - l][j - k]) goto nothing;
     27                         if (c != col[i][j - l] - col[i - k][j - l]) goto nothing;
     28                         d1 += grid[i - k + l][j - k + l];
     29                         d2 += grid[i - l - 1][j - k + l];
     30                     }
     31 
     32                     if (d1 != d2 || d1 != r) goto nothing;
     33 
     34                     return k;
     35                 nothing:;
     36                 }
     37             }
     38         }
     39 
     40         return 1;
     41     }
     42 };