网格中的幻方在 C++ 中

假设我们有一个网格，我们必须找到该网格中魔法正方形子网格的数量。一个魔法正方形是一个 3 x 3 网格，里面填有从 1 到 9 的不同数字，使得每一行、每一列和两条对角线上的数字总和都相同。

因此，如果输入如下：

4384
9519
2762

则输出为 1，因为魔法正方形是

438
951
276

为了解决这个问题，我们将遵循以下步骤：

  • 用值定义一个集合：[816357492, 834159672, 618753294, 672159834, 492357816, 438951276, 294753618, 276951438]
  • 定义大小为：9 x 2 的偏移数组：{{ -2,-2},{-2,-1},{-2,0},{-1,-2},{-1,-1},{-1,0},{0,-2},{0,-1},{0,0}}
  • ans := 0
  • 对于初始化 i := 2，当 i < grid 行计数时，更新（将 i 增加 1），执行 -
    • 对于初始化 j := 2，当 j < grid 行计数时，更新（将 j 增加 1），执行 -
      • sum := 0
      • 对于初始化 k := 0，当 k < 9 时，更新（将 k 增加 1），执行 -
        • sum := sum * 10
        • sum := 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;
   }
};
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

更新于： 04-7 月-2020

231 视图

开启您的 职业生涯

完成课程即可获得认证

开始
广告