题目

一个魔法方块是一个3x3的矩阵，矩阵内的每个值是1-9的不重复数字，并且其每行，每列和对角线的和都相等。

给一个整数矩阵，找出这个矩阵中有多少个上面说的魔法方快。（每一个子矩阵都是连续的）。

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 <= gridi <= 15

思路

由于我们需要判断3x3的矩阵是否1-9的唯一值，我们只能通过遍历来搞定，因此，目前我暂时还没有找到一个更好的办法，n^2的时间复杂度是没办法避免的了。

通过对3x3矩阵的描述来看，其实我们可以知道有这么几个特征：

  1. 矩阵的值是1-9不重复的
  2. 为了行列对角线都是相等，中间的那个值必须要为5

因此，我们可以在判断一个矩阵是不是的时候通过这两个条件加速一下，避免不必要的判断。代码如下：

func numMagicSquaresInside(grid [][]int) int {
    if len(grid) < 3 || len(grid[0]) < 3 {
        return 0
    }

    rowLength := len(grid[0])
    columnLength := len(grid)

    find := 0
    for column := 0; column+2 < columnLength; column++ {
        for row := 0; row+2 < rowLength; row++ {
            // 找到起点
            if isMagicSquare(grid, column, row) {
                find++
            }
        }
    }

    return find
}

// 暴力破解查找
func isMagicSquare(grid [][]int, column, row int) bool {
    // 中间不为5肯定不是
    if grid[column+1][row+1] != 5 {
        return false
    }
    num := make([]int, 9, 9)
    for i := column; i < 3+column; i++ {
        for j := row; j < 3+row; j++ {
            // 数字必须为1-9，且只能出现一次
            if grid[i][j] > 9 || grid[i][j] < 1 {
                return false
            }
            num[grid[i][j]-1]++
            if num[grid[i][j]-1] > 1 {
                return false
            }

            if j == row {
                // 右
                if 15 != grid[i][j]+grid[i][j+1]+grid[i][j+2] {
                    return false
                }
                // 右上
                if i == 2+column {
                    if 15 != grid[i][j]+grid[i-1][j+1]+grid[i-2][j+2] {
                        return false
                    }
                }
            }

            // 下
            if i == column {
                if 15 != grid[i][j]+grid[i+1][j]+grid[i+2][j] {
                    return false
                }

                // 右下
                if j == row {
                    if 15 != grid[i][j]+grid[i+1][j+1]+grid[i+2][j+2] {
                        return false
                    }
                }
            }
        }
    }

    return true
}

完整代码见：https://github.com/scofieldpeng/leetcode/blob/master/numMagicSquaresInside/numMagicSquaresInside.go

原题目见: https://leetcode.com/problems/magic-squares-in-grid/