leetcode

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