이 문제에서 크기가 n인 2차원 행렬 mat[][]가 주어지며, n은 홀수입니다. 우리의 임무는 행렬에서 정사각형의 최대 변 길이를 찾는 것입니다.
문제 설명 − 둘레 값이 동일하고 행렬과 같은 중심을 공유하는 정사각형 행렬의 길이를 찾아야 합니다.
문제를 이해하기 위해 예를 들어 보겠습니다.
입력
mat[][] = {
{2, 4, 6, 6, 5},
{1, 7, 7, 7, 3},
{5, 7, 0, 7, 1},
{3, 7, 7, 7, 1},
{2, 0, 1, 3, 2}
} 출력
3
솔루션 접근 방식
문제에 대한 간단한 솔루션은 행렬의 중심 요소를 찾는 것입니다. 홀수 행렬이므로 중심 요소는 인덱스(n/2, n/2)에 있습니다. 중심을 찾은 후 모든 2D 하위 요소를 찾을 수 있습니다. 모든 요소가 동일한지 확인하는 주변 행렬입니다.
중심에서 떨어진 인덱스 i의 부분행렬은 인덱스 (n/2 - 1)에서 (n/2 + 1)까지 행(n/2 - 1) 및 (n/2 + 1)의 요소를 갖습니다. 또한 인덱스(n/2 - 1)에서 (n/2 + 1)까지의 열(n/2 - 1) 및 (n/2 + 1) 요소가 둘레에 포함됩니다. 0에서 n/2까지의 i 값에 대한 부분행렬이 모든 둘레 요소가 동일한지 확인해야 합니다.
우리 솔루션의 작동을 설명하는 프로그램
예시
#include <iostream>
#define n 5
using namespace std;
int findMaxSideSquare(int matrix[][n]) {
int squareLen = 1;
for (int i = 0; i < n / 2; i++) {
int sideVal = matrix[i][i];
bool isSquare = true;
for (int j = i; j < n - i; j++) {
if (matrix[i][j] != sideVal)
isSquare = false;
if (matrix[n - i - 1][j] != sideVal)
isSquare = false;
if (matrix[j][i] != sideVal)
isSquare = false;
if (matrix[j][n - i - 1] != sideVal)
isSquare = false;
}
if (isSquare)
squareLen = n - 2 * i;
}
return squareLen;
}
int main() {
int mat[n][n] = {
{2, 4, 6, 6, 5},
{1, 7, 7, 7, 3},
{5, 7, 0, 7, 1},
{3, 7, 7, 7, 1},
{2, 0, 1, 3, 2}
};
cout<<"The maximum side length of square in a Matrix is "<<findMaxSideSquare(mat);
return 0;
} 출력
The maximum side length of square in a Matrix is 3