C ++中的网格中的魔术方块
假设我们有一个网格,我们必须找到该网格中魔方子网格的数量。魔方是一个3x3的网格,其中填充了从1到9的不同数字,因此每一行,每一列和两个对角线的总和都相同。
所以,如果输入像
4
8
9
1
2
6
那么输出将为1,因为魔方是
4
8
1
为了解决这个问题,我们将遵循以下步骤-
定义一组值:[816357492、834159672、618753294、672159834、492357816、438951276、294753618、276951438]
定义一个大小为9x2的数组偏移量:={{-2,-2},{-2,-1},{-2,0},{-1,-2},{-1,-1},{-1,0},{0,-2},{0,-1},{0,0}}
回答:=0
对于初始化i:=2,当i<网格行数时,更新(将i增加1),执行-
和:=0
对于初始化k:=0,当k<9时,更新(将k增加1),-
ans:=ans+s中和的出现
总和:=总和*10
sum:=sum+grid[i+offset[k,0],j+offset[k,1]]
对于初始化j:=2,当j<网格行数时,更新(j增加1),-
返回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; } }; 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