그리드에 마방진 하위 그리드의 수를 찾아야 하는 그리드가 있다고 가정합니다. 마방진은 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의 합계 발생
- j 초기화의 경우 :=2, j <그리드 행 개수일 때 업데이트(j를 1만큼 증가), −
- 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#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