우리는 숫자의 행렬로 주어진다. 목표는 주어진 행렬 내부에 존재하는 마방진의 수를 찾는 것입니다.
매직 스퀘어는 행렬로 간주하면 스도쿠의 그리드처럼 1에서 9 사이의 요소를 포함하는 3X3 행렬입니다. 속성은 -
- 모든 숫자는 정확히 한 번 나타납니다.
- 행렬에 있는 9개 셀의 합은 45입니다.
- 3의 각 행의 합은 15입니다.
- 3의 각 열의 합은 15입니다.
- 3의 대각선의 합은 5입니다.
- 이러한 합계를 얻으려면 5가 항상 두 대각선의 중간에 있어야 합니다.
입력
int arr[][]= { { 1,2,3,0 }, { 4,5,6,1 }, { 7,8,9,0 } }; 출력
Magic Squares present: 0
설명 − 이해할 수 있는 행렬 형태 만들기 −
| 1 | 2 | 3 | 0 |
| 4 | 5 | 6 | 1 |
| 7 | 8 | 9 | 0 |
모든 요소는 1에서 9 사이이며 고유합니다. 하지만
1+2+3=6 !=4+5+6=15 !=7+8+9=23
또한 대각선 합이 15와 같지 않습니다.
입력
arr[][]= { { 1,2,3,0 }, { 4,5,6,1 }, { 7,8,9,0 } }; 출력
Magic Squares present : 1
설명 − 이해할 수 있는 행렬 형태 만들기 −
| 1 | 6 | 8 | 4 |
| 8 | 1 | 6 | 0 |
| 3 | 5 | 7 | 1 |
| 4 | 9 | 2 | 0 |
모든 숫자는 고유하며 범위는 1에서 9입니다.
행 합계, 8+1+6=3+5+7=4+9+2=15
열 합계, 8+3+4=1+5+9=6+7+2=15
대각선 합, 8+5+2=4+5+6=15
또한 1에서 9를 더하면 45가 되고 5는 두 대각선의 중간입니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
정수 배열 Grid[][]는 숫자를 저장하고 행과 열은 차원을 저장합니다.
-
함수 magicSquare(int a, int b…..int i)는 9개의 요소를 모두 입력으로 받아 마방진을 만드는지 확인합니다. 마방진이면 1을 반환하고, 그렇지 않으면 1을 반환합니다.
-
여기서 우리는 모든 매개변수를 저장하기 위해 배열 arr[9]를 사용하고 고유한 셀을 차지하는지 확인하여 고유한지 확인합니다. 셀에 count<1이 있으면 아니오를 의미합니다. 1에서 9 사이의 범위가 아니거나 count>1이면 아니오입니다. 고유하지 않습니다. 플래그=0 설정
-
플래그가 1이면 행, 열, 대각선 합계가 15인지 확인합니다. true이면 마법의 정사각형입니다. 1을 반환하지 않으면 0을 반환합니다.
-
함수 countSquares(int G[3][4],int R, int C)는 그리드, 행과 열을 입력으로 사용하여 번호를 계산합니다. 그 안에 있는 마방진의 수.
-
Count는 이러한 사각형의 수를 저장하는 데 사용됩니다.
-
첫 번째 요소에서 행-2, 열-2(3X3 행렬)까지 순회 시작
-
대각선 G[i+1][j+1]의 중간이 5가 아니면 마방진이 불가능하므로 현재 반복을 건너뛰십시오.
-
그렇지 않으면 9개의 요소를 모두 magicSquare( int a to i )에 전달하여 확인합니다.
-
G[i][j]를 포함한 9개의 요소는 모두 G[i+1][j], G[i+2][j], G[i+1][j+1], G[i][j입니다. +1],G[i][j+2],G[i+2][j+2],G[i+2][j+1], G[i+1][j+2]
-
1을 반환하면 카운트가 증가합니다.
-
결국 원하는 결과로 카운트를 반환합니다.
예시
#include <bits/stdc++.h>
using namespace std;
// to check is subgrid is Magic Square
int magicSquare(int a, int b, int c, int d, int e,
int f, int g, int h, int i){
int flag=1; // to mark all numbers are unique and between 1 to 9
int arr[9]={0};
arr[a-1]++;
arr[b-1]++;
arr[c-1]++;
arr[d-1]++;
arr[e-1]++;
arr[f-1]++;
arr[g-1]++;
arr[h-1]++;
arr[i-1]++;
for(int i=0;i<9;i++)
if(arr[i]>1 || arr[i]<1) //every number occurs exactly once{
flag=0;
break;
}
// checking all sums as 15
if (flag==1 && (a + b + c) == 15 && (d + e + f) == 15 && (g + h + i) == 15 && (a + d + g) == 15 &&(b + e + h) == 15 && (c + f + i) == 15 &&(a + e + i) == 15 && (c + e + g) == 15)
return 1;
return 0;
}
int countSquares(int G[3][4],int R, int C){
int count = 0;
for (int i = 0; i < R - 2; i++)
for (int j = 0; j < C - 2; j++) {
if (G[i + 1][j + 1] != 5)
continue;
int ismagic=magicSquare(G[i][j], G[i][j + 1], G[i][j + 2], G[i + 1][j], G[i + 1][j + 1],
G[i + 1][j + 2], G[i + 2][j], G[i + 2][j + 1], G[i + 2][j + 2]);
// check for magic square subgrid
if (ismagic==1)
count++;
}
return count;
}
int main(){
int Grid[3][4] = { { 4, 3, 8, 4 },{ 9, 5, 1, 9 },{ 2, 7, 6, 2 } };
int row=3;
int col=4;
cout <<"Count of Magic Squares in Grid: "<<countSquares(Grid,row,col);
return 0;
} 출력
Count of Magic Squares in Grid: 1