840. Magic Squares In Grid

题目描述和难度

  • 题目描述：

3 x 3 的幻方是一个填充有从 1 到 9 的不同数字的 3 x 3 矩阵，其中每行，每列以及两条对角线上的各数之和都相等。

给定一个由整数组成的 N × N 矩阵，其中有多少个 3 × 3 的 “幻方” 子矩阵？（每个子矩阵都是连续的）。

 

示例 1:

输入: [[4,3,8,4],
      [9,5,1,9],
      [2,7,6,2]]
输出: 1
解释: 
下面的子矩阵是一个 3 x 3 的幻方：
438
951
276

而这一个不是：
384
519
762

总的来说，在本示例所给定的矩阵中只有一个 3 x 3 的幻方子矩阵。

提示:

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

思路分析

求解关键：

参考解答

参考解答1

public class Solution {

    public int numMagicSquaresInside(int[][] grid) {
        int row = grid.length;
        if (row == 0) {
            return 0;
        }
        int col = grid[0].length;
        if (row < 3 || col < 3) {
            return 0;
        }

        int res = 0;
        int[] temp = new int[8];
        // 找中心是 5 的矩阵
        for (int i = 1; i < row - 1; i++) {
            for (int j = 1; j < col - 1; j++) {
                System.out.println(i + " " + j);
                if (magicSquares(grid, temp, i, j)) {
                    res++;
                }
            }
        }
        return res;
    }

    // 以坐标 i j 为中心的矩阵是不是河图矩阵
    private boolean magicSquares(int[][] grid, int[] temp, int i, int j) {
        if (grid[i][j] != 5) {
            return false;
        }

        for (int k = 0; k < 3; k++) {
            for (int l = 0; l < 3; l++) {
                if (grid[i - 1 + k][j - 1 + l] < 1 || grid[i - 1 + k][j - 1 + l] > 9) {
                    return false;
                }
            }
        }

        temp[0] = grid[i - 1][j - 1] + grid[i - 1][j] + grid[i - 1][j + 1];
        if (temp[0] != 15) {
            return false;
        }
        temp[1] = grid[i][j - 1] + grid[i][j] + grid[i][j + 1];
        if (temp[1] != 15) {
            return false;
        }
        temp[2] = grid[i + 1][j - 1] + grid[i + 1][j] + grid[i + 1][j + 1];
        if (temp[2] != 15) {
            return false;
        }
        temp[3] = grid[i - 1][j - 1] + grid[i][j - 1] + grid[i + 1][j - 1];
        if (temp[3] != 15) {
            return false;
        }
        temp[4] = grid[i - 1][j] + grid[i][j] + grid[i + 1][j];
        if (temp[4] != 15) {
            return false;
        }
        temp[5] = grid[i - 1][j + 1] + grid[i][j + 1] + grid[i + 1][j + 1];
        if (temp[5] != 15) {
            return false;
        }
        temp[6] = grid[i - 1][j - 1] + grid[i][j] + grid[i + 1][j + 1];
        if (temp[6] != 15) {
            return false;
        }
        temp[7] = grid[i + 1][j - 1] + grid[i][j] + grid[i - 1][j + 1];
        if (temp[7] != 15) {
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        int[][] grid = new int[][]{
                {5, 2, 9, 5, 4},
                {8, 1, 6, 1, 4},
                {7, 2, 4, 7, 8},
                {1, 8, 3, 5, 9},
                {5, 7, 2, 6, 1}};

        Solution solution = new Solution();
        int numMagicSquaresInside = solution.numMagicSquaresInside(grid);
        System.out.println(numMagicSquaresInside);
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0840-magic-squares-in-grid ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。