Description

A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum.

Given an grid of integers, how many 3 x 3 "magic square" subgrids are there? (Each subgrid is contiguous).

Example 1:

Input: [[4,3,8,4],
[9,5,1,9],
[2,7,6,2]]
Output: 1
Explanation:
The following subgrid is a 3 x 3 magic square:
438
951
276

while this one is not:
384
519
762

In total, there is only one magic square inside the given grid.

Note:

1. 1 <= grid.length <= 10
2. 1 <= grid[0].length <= 10
3. 0 <= grid[i][j] <= 15

Solution

Iteration, O(n ^ 2), S(1)

没什么特别的办法，就是枚举3 * 3 grid的坐上坐标，然后计算当前grid isMagic。

class Solution {
    public int numMagicSquaresInside(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        
        int m = grid.length;
        int n = grid[0].length;
        int count = 0;
        
        for (int i = 0; i < m - 2; ++i) {
            for (int j = 0; j < n - 2; ++j) {
                if (isMagic(grid[i][j], grid[i][j + 1], grid[i][j + 2]
                           , grid[i + 1][j], grid[i + 1][j + 1], grid[i + 1][j + 2]
                           , grid[i + 2][j], grid[i + 2][j + 1], grid[i + 2][j + 2])) {
                    ++count;
                }
            }
        }
        
        return count;
    }
    
    private boolean isMagic(int... vals) {
        int[] count = new int[16];  // because 0 <= grid[i][j] <= 15
        for (int v : vals) {
            ++count[v];
        }
        
        for (int v = 1; v <= 9; ++v) {
            if (count[v] != 1) {
                return false;
            }
        }
        
        return vals[0] + vals[1] + vals[2] == 15
            && vals[3] + vals[4] + vals[5] == 15
            && vals[6] + vals[7] + vals[8] == 15
            && vals[0] + vals[3] + vals[6] == 15
            && vals[1] + vals[4] + vals[7] == 15
            && vals[2] + vals[5] + vals[8] == 15
            && vals[0] + vals[4] + vals[8] == 15
            && vals[2] + vals[4] + vals[6] == 15;
    }
}