이 문제에서는 NxN 이진 행렬 bin[][]이 제공됩니다. 우리의 임무는 이진 행렬에서 모든 1이 이루는 가장 큰 '+'의 크기를 찾는 것입니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력
0 1 1 1 1 1 0 1 0
출력
5
솔루션 접근 방식
문제에 대한 간단한 해결책은 주어진 1에 대해 네 방향 모두에서 동일해야 하는 행렬의 한 점에 대해 한 방향에서 최대 1 수를 찾아야 하는 가장 큰 '+'를 찾는 것입니다. 이를 위해, 우리는 점의 각 변에 대해 하나의 행렬, 즉 4를 생성할 것입니다. 각각은 주어진 요소에 대해 연속 1의 수를 저장합니다. 모든 인덱스 값에 대해 네 방향에서 연속된 모든 값의 최소값인 최대값을 찾습니다.
우리 솔루션의 작동을 설명하는 프로그램
예시
#include <iostream>
using namespace std;
#define N 7
int findLargestPlusSize(int mat[N][N]) {
int conOneLeft[N][N], conOneRight[N][N], conOneTop[N][N], conOneBottom[N][N];
for (int i = 0; i < N; i++) {
conOneTop[0][i] = mat[0][i];
conOneBottom[N - 1][i] = mat[N - 1][i];
conOneLeft[i][0] = mat[i][0];
conOneRight[i][N - 1] = mat[i][N - 1];
}
for (int i = 0; i < N; i++) {
for (int j = 1; j < N; j++) {
if (mat[i][j] == 1)
conOneLeft[i][j] = conOneLeft[i][j - 1] + 1;
else
conOneLeft[i][j] = 0;
if (mat[j][i] == 1)
conOneTop[j][i] = conOneTop[j - 1][i] + 1;
else
conOneTop[j][i] = 0;
j = N - 1 - j;
if (mat[j][i] == 1)
conOneBottom[j][i] = conOneBottom[j + 1][i] + 1;
else
conOneBottom[j][i] = 0;
if (mat[i][j] == 1)
conOneRight[i][j] = conOneRight[i][j + 1] + 1;
else
conOneRight[i][j] = 0;
j = N - 1 - j;
}
}
int maxConOne = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++){
int ConOnes = min(min(conOneTop[i][j],
conOneBottom[i][j]), min(conOneLeft[i][j], conOneRight[i][j]));
if(ConOnes > maxConOne)
maxConOne = ConOnes;
}
}
if (maxConOne)
return (4 * (maxConOne - 1) + 1);
return 0;
}
int main() {
int mat[N][N] = {
{ 1, 0, 1, 1, 1, 1, 0 },
{ 1, 0, 1, 0, 1, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 0 },
{ 0, 0, 0, 0, 1, 0, 0 },
{ 1, 0, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 1 },
{ 1, 0, 0, 0, 1, 0, 0 },
};
cout<<"The size of the largest plus formed by ones is "<<findLargestPlusSize(mat);
return 0;
} 출력
The size of the largest plus formed by ones is 9