# LeetCode - 1895. Largest Magic Square
### 題目網址：https://leetcode.com/problems/largest-magic-square/
###### tags: `LeetCode` `Medium` `陣列` `窮舉` `模擬`

/*
    -LeetCode format-
    Problem: 1895. Largest Magic Square
    Difficulty: Medium
    
    by Inversionpeter
*/



class Solution {
public:
    int largestMagicSquare(vector<vector<int>>& grid) {
        int rows = grid.size(), columns = grid[0].size(), candidate = min(rows, columns), rowSums[50][51] = {}, columnSums[50][51] = {}, theSum, diagonal1, diagonal2;
        bool valid;
        for (int i = 0; i < rows; ++i)
            for (int j = 0; j < columns; ++j) {
                rowSums[i][j + 1] = rowSums[i][j] + grid[i][j];
                columnSums[j][i + 1] = columnSums[j][i] + grid[i][j];
            }
        for (; candidate > 1; --candidate) {
            for (int i = 0; i <= rows - candidate; ++i)
                for (int j = 0; j <= columns - candidate; ++j) {
                    valid = true;
                    theSum = rowSums[i][j + candidate] - rowSums[i][j];
                    for (int k = 0; k < candidate; ++k)
                        if (theSum != rowSums[i + k][j + candidate] - rowSums[i + k][j] || theSum != columnSums[j + k][i + candidate] - columnSums[j + k][i]) {
                            valid = false;
                            break;
                        }
                    if (valid) {
                        diagonal1 = diagonal2 = 0;
                        for (int k = 0; k < candidate; ++k) {
                            diagonal1 += grid[i + k][j + k];
                            diagonal2 += grid[i + k][j + candidate - k - 1];
                        }
                        if (diagonal1 == theSum && diagonal2 == theSum)
                            return candidate;
                    }
                }
        }
        return 1;
    }
};