मान लीजिए हमारे पास एक ग्रिड है, हमें उस ग्रिड में मैजिक स्क्वेयर सब-ग्रिड की संख्या ढूंढनी है। एक मैजिक स्क्वेयर एक 3 x 3 ग्रिड है जो 1 से 9 तक की अलग-अलग संख्याओं से भरा होता है जैसे कि प्रत्येक पंक्ति, कॉलम, और दोनों विकर्णों का योग समान हो।
इसलिए, यदि इनपुट जैसा है:
| 4 | 3 | 8 | 4 |
| 9 | 5 | 1 | 9 |
| 2 | 7 | 6 | 2 |
तो आउटपुट 1 होगा, क्योंकि मैजिक स्क्वेयर है:
| 4 | 3 | 8 |
| 9 | 5 | 1 |
| 2 | 7 | 6 |
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
- मानों के साथ एक सेट परिभाषित करें:
[816357492, 834159672, 618753294, 672159834, 492357816, 438951276, 294753618, 276951438] - आकार 9 x 2 का एक सरणी
offsetपरिभाषित करें:{{-2,-2},{-2,-1},{-2,0},{-1,-2},{-1,-1},{-1,0},{0,-2},{0,-1},{0,0}} ans := 0i := 2सेग्रिड पंक्ति संख्या - 1तक लूप चलाएं:j := 2सेग्रिड कॉलम संख्या - 1तक लूप चलाएं:sum := 0k := 0से8तक लूप चलाएं:sum := sum * 10sum := sum + grid[i + offset[k][0]][j + offset[k][1]]
ans := ans + s में sum की घटनाएं
ansवापस करें
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numMagicSquaresInside(vector<vector<int>>& grid) {
const unordered_set<int> s{816357492, 834159672, 618753294,
672159834,492357816, 438951276, 294753618,276951438};
const int offset[][2] = {{-2, -2}, {-2, -1}, {-2, 0},{-1, -2}, {-1, -1}, {-1, 0}, { 0, -2}, { 0, -1}, { 0, 0}};
int ans = 0;
for(int i = 2; i< grid.size(); i++)
{
for(int j = 2; j<grid.size(); j++)
{
int sum = 0;
for(int k = 0; k<9; k++)
{
sum *= 10;
sum += grid[i + offset[k][0]][j+offset[k][1]];
}
ans += s.count(sum);
}
}
return ans;
}
};
int main(){
Solution ob;
vector<vector<int>> v = {{4,3,8,4},{9,5,1,9},{2,7,6,2}};
cout << (ob.numMagicSquaresInside(v));
}
इनपुट
{{4,3,8,4},{9,5,1,9},{2,7,6,2}}
आउटपुट
1