Home  >  Article  >  Backend Development  >  . Magic Squares In Grid

. Magic Squares In Grid

王林
王林Original
2024-08-10 06:44:32356browse

840. Magic Squares In Grid

Medium

Topics: Array, Hash Table, Math, Matrix

A 3 x 3 magic square is a3 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 a row x col grid of integers, how many 3 x 3 contiguous magic square subgrids are there?

Note: while a magic square can only contain numbers from 1 to 9, grid may contain numbers up to 15.

Example 1:

. Magic Squares In Grid

  • Input: grid = [[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:

. Magic Squares In Grid

while this one is not:

. Magic Squares In Grid

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

Example 2:

  • Input: grid = [[8]]
  • Output: 0

Constraints:

  • row == grid.length.
  • col == grid[i].length
  • 1 <= row, col <= 10
  • 0 <= grid[i][j] <= 15

Solution:

We need to count how many 3x3 contiguous subgrids in the given grid form a magic square. A magic square is a 3x3 grid where all rows, columns, and both diagonals sum to the same value, and it contains the distinct numbers from 1 to 9.

To solve this problem, we can follow these steps:

  1. Check if a Subgrid is Magic:

    • The subgrid must contain all distinct numbers from 1 to 9.
    • The sum of each row, column, and diagonal should be 15.
  2. Iterate through the Grid:

    • Since we need to check 3x3 subgrids, we will iterate from 0 to row-2 for rows and from 0 to col-2 for columns.
    • For each top-left corner of the 3x3 subgrid, extract the subgrid and check if it's a magic square.

Let's implement this solution in PHP: 840. Magic Squares In Grid






Explanation:

  1. isMagic function:

    • Extracts the 3x3 subgrid.
    • Checks if all numbers are distinct and between 1 to 9.
    • Verifies that the sums of the rows, columns, and diagonals are all 15.
  2. numMagicSquaresInside function:

    • Iterates over all possible 3x3 subgrids in the given grid.
    • Counts how many of those subgrids are magic squares.

This code works efficiently within the constraints, counting all 3x3 magic square subgrids in the given grid.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

  • LinkedIn
  • GitHub

The above is the detailed content of . Magic Squares In Grid. For more information, please follow other related articles on the PHP Chinese website!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn