Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++에서 그리드의 매직 스퀘어

<시간/>

그리드에 마방진 하위 그리드의 수를 찾아야 하는 그리드가 있다고 가정합니다. 마방진은 1에서 9까지의 고유한 숫자로 채워진 3 x 3 그리드로 각 행, 열 및 두 대각선의 합이 모두 동일합니다.

따라서 입력이 다음과 같으면

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 :={{-2,-2},{-2,-1},{-2,0},{-1,-2},{-1 ,-1},{-1,0},{0,-2},{0,-1},{0,0}}
  • ans :=0
  • 초기화 i의 경우:=2, i <그리드 행 개수일 때 업데이트(i를 1만큼 증가), 수행 -
    • j 초기화의 경우 :=2, j <그리드 행 개수일 때 업데이트(j를 1만큼 증가), −
      • 합계 :=0
      • 초기화 k의 경우:=0, k <9일 때 업데이트(k를 1만큼 증가), 수행 -
        • 합계 :=합 * 10
        • 합계 :=합 + 그리드[i + 오프셋[k, 0], j + 오프셋[k, 1]]
      • ans :=as + s의 합계 발생
  • 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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