leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1895.cpp (1394B)

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