Maximize the Magic Square in the Matrix of Ricochet

HELLO, hello everyone, I am Dumb 🙈🙈🙈
Today Dumb continues to record the process of Likou brushing questions, which is included in the column algorithm 😜😜😜

This column is based on different categories of tags, and each tag is divided into three levels: Easy, Medium, and Hard 👊👊👊

All the questions in this part are from LeetCode, and the link to the original LeetCode question is marked under each question 🏃🏃🏃

OK, brothers, don’t talk nonsense and go straight to the topic, go ahead 🌞🌞🌞

A 🏠 topic description

840. Magic Squares in Matrices

A 3 x 3 magic square is a 3 x 3 matrix filled with different numbers from 1 to 9, where the sum of the numbers in each row, column and both diagonals is equal.

Given a row x col grid of integers, how many 3 × 3 "magic square" submatrices are there? (each sub-matrix is ​​contiguous).

Example 1:

enter: grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]
output: 1
 explain: 
The following submatrix is ​​a 3 x 3 The magic square:

And this one is not:

Overall, there is only one 3 in the given matrix for this example x 3 The magic square submatrix of .

Example 2:

output: grid = [[8]]
enter: 0

hint:

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

Two 🏠Thoughts to solve the problem

2.1 🚀 Key information

The first step in solving the problem is of course to extract the key information of the title literal 😎😎😎

A 3 x 3 magic square is a 3 x 3 matrix of different numbers from 1 to 9, the sum of each row, column and two diagonals is equal. Given a matrix, find how many 3 × 3 magic square submatrices are in it

From the title, it is easy to know that the 3 × 3 magic square must be a different number from 1 to 9 (the first time the error is solved and it is greater than 9, the review must be careful 😭😭😭)

For a 3 × 3 magic square, its central element must be 5, so when traversing the input matrix, only the central element needs to be traversed, so the loop condition is [ 1 , len - 1 )

After extracting the key information in the topic, go directly to the second stage and organize your thoughts 😃😃😃

2.2 🚀 Organize ideas

Brute Force: Check each 3x3 grid separately

For each grid, all numbers must be different and between 1 and 9, and the sum of each row, column, and diagonal must be the same 🌷🌷🌷

nitty gritty:

① When traversing the input matrix, you only need to traverse the central element

② When the judgment numbers must be different and are between 1 and 9, the maximum value only needs to be in [ 1 , 9 ]

Rotation method: the third-order magic square solution is fixed, and there are the following eight types

The common points of the eight solutions are that the middle elements are five, the corner elements are all even numbers, and the midpoints are all odd numbers. The solution of the same row can be obtained by rotation, the first row is mirrored, and the second row can be obtained. In other words, there is only one solution to the third-order magic square, and the rest are the reflections of rotating mirror images

implement logic

1. According to the above, only when the central element is five, can it be judged whether it is a magic square

2. At this time, you only need to compare the remaining eight elements. Due to the rotation invariant property of the solution, store the eight elements in order to facilitate later comparison. The order is as shown in the figure below

3. How to rotate the mirror image, refer to this 189. Rotate array The idea of ​​​​putting the front part to the back can achieve the rotation effect, and the mirror image only needs to iterate in reverse

4. In the second step, compare the first element of the input array with 8 6 2 4 one by one, take out the two solutions of the forward mirror image from the target array and compare whether it is one, and then determine whether it is a magic square 🐌🐌🐌

Note: source of rotation , with some deletions

After sorting out the problem-solving ideas, directly enter the third stage, and the code is realized 😃😃😃

Three 🏠 code explanation

3.1 🚀 Code implementation

According to our idea of ​​breaking the problem just now, let’s go directly to the code 👇👇👇👇

bool isMagic(std::vector<int>& tmpVec) {
	for (int targetIndex = 0; targetIndex < 8; targetIndex += 2) { //Iterate through the temporary array
		if (tmpVec[0] == targetVec[targetIndex]) { //The first element of the input array is compared with 8 6 2 4 one by one
			//Take out the forward mirroring two solutions from the target array and compare whether it is one
            return tmpVec == std::vector<int>(targetVec.begin() + targetIndex, targetVec.begin() + targetIndex + 8) || tmpVec == std::vector<int>(targetVec.rbegin() + 7 - targetIndex, targetVec.rbegin() + 15 - targetIndex);
		}
	}
	return false;
}

//Initialize target array
std::vector<int> targetVec = { 8, 1, 6, 7, 2, 9, 4, 3, 8, 1, 6, 7, 2, 9, 4, 3 };

int numMagicSquaresInside(std::vector<std::vector<int>>& grid) {
	//Initialize matrix x-axis, y-axis corresponds to offset
	std::vector<std::pair<int, int>> offsetVals = { { -1, -1 }, { -1, 0 }, 
            { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 } };
    
    //Initialize the return value, row and column length
	int count = 0, rows = grid.size() - 1, columns = grid[0].size() - 1;
    //Initialize the temporary array
	std::vector<int> tmpVec(8);
	for (int i = 1; i < rows; ++i) { //iterate over rows
		for (int j = 1; j < columns; ++j) { //iterate over columns
			if (grid[i][j] == 5) {  //If the central element is 5
				for (int index = 0; index < 8; ++index) { 
					tmpVec[index] = grid[i + offsetVals[index].first][j + offsetVals[index].second];  //places the eight elements centered at i,j in a tmpVec 
				}
				count += isMagic(tmpVec);  //and determine whether it is a magic square
			}
		}
	}
	return count;  //return result
}

3.2 🚀 Detailed analysis

After reading 👀👀👀 full-annotated version of the code implementation, I believe that the general logic is capitalized OK. 😃😃😃

Then we dig out the obscure details of the above implementation 😖😖😖 to analyze it, start working directly, and walk up 👇👇👇👇

targetIndex += 2 

The first element of the input array (tmpVec) is compared with 8 6 2 4 one by one, so the index moves by two places 🐳🐳🐳

tmpVec == std::vector<int>(targetVec.begin() + i , targetVec.begin() + i + 8);

Rotation logic: After finding the target position, move eight bits from the current position to the current position (positive direction)

tmpVec == std::vector<int>(targetVec.rbegin() + 7 - i, targetVec.rbegin() + 15 - i);

Mirror logic: After finding the target position, from reverse iteration 7 - i to reverse iteration 15 - i (reverse) 🌼🌼🌼

//For example to find the first 2, for mirroring it is [ 2, 7, 6, 1, 8, 3, 4, 9 ]
//That is, the distance of 3, 4, 9, 2 of reverse iteration 7 - 4 = 3 (targetVec.rbegin() + 7 - i) 
[ 8, 1, 6, 7, 2, 9, 4, 3, 8, 1, 6, 7, 2, 9, 4, 3 ]

Four 🏠 mental journey

In order to make it easier for readers to understand the blogger’s real process of brushing questions, I have restored the pure and true state at that time and recorded it in the section of mental journey. Those who are not interested can skip it directly.

There is no problem for bloggers to extract 🚀 key information in the first stage, and there is no problem in organizing 🚀 ideas in the second stage

The code was implemented using a violent solution (the solution to the problem on the official website is the same as violence, and the rotation method is really hard to imagine), the simplicity is poor 😭😭😭, the code is as follows 👇👇👇👇

int numMagicSquaresInside(vector<vector<int>>& grid) {
        int count = 0;
	    int width = grid.size(), high = grid[0].size();
        for (int i = 1; i < width - 1; ++i) { //Iterate over the width of the 2D input
            for (int j = 1; j < high - 1; ++j) {
                if (grid[i][j] != 5) continue;
                if (grid[i-1][j] == grid[i][j]) continue; 	//Each value is different
                
                //horizontal summation
                if (grid[i-1][j-1] + grid[i][j-1] + grid[i+1][j-1] != 15) continue;
                if (grid[i-1][j] + grid[i][j] + grid[i + 1][j] != 15) continue;
                if (grid[i-1][j+1] + grid[i][j+1] + grid[i+1][j+1] != 15) continue;
                
                //vertical sum
                if (grid[i-1][j-1] + grid[i-1][j] + grid[i-1][j+1] != 15) continue;
                if (grid[i][j-1] + grid[i][j] + grid[i][j+1] != 15) continue;
                if (grid[i+1][j-1] + grid[i+1][j] + grid[i+1][j+1] != 15) continue;
                
                //Diagonal sum
                if (grid[i-1][j-1] + grid[i][j] + grid[i+1][j+1] != 15) continue;
                if (grid[i-1][j+1] + grid[i][j] + grid[i+1][j-1] != 15) continue;
                
                //find the maximum and minimum legalScope
                int mem_max = std::max({grid[i-1][j-1], grid[i][j-1], grid[i+1][j-1],
                                grid[i-1][j], grid[i][j], grid[i+1][j],
                                grid[i-1][j+1], grid[i][j+1], grid[i+1][j+1]});

                int mem_min = std::min({grid[i-1][j-1], grid[i][j-1], grid[i+1][j-1],
                    grid[i-1][j], grid[i][j], grid[i+1][j],
                    grid[i-1][j+1], grid[i][j+1], grid[i+1][j+1]});

                if (mem_max <= 9 && mem_min >= 1) ++count;
            }
        }
	    return count;
    }

Five 🏠 Conclusion

In this impetuous society, but have the patience to see this, you must be a very powerful person 👍👍👍

If you think the article is helpful, don’t forget to like + follow, your encouragement is my biggest motivation

The blogger will continue to update more high-quality content, come on! Technician! 💪💪💪