BOJ #1051, 숫자 정사각형 문제입니다.
입력 범위를 general하게 바라보면 계산량이 좀 많습니다만 입력 범위가 매우 작아서(N, M <= 50) 시간 초과가 나지 않습니다. 간단하게 브루트포스로 해결할 수 있습니다.
더보기
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
void getMatrixInput(int** matrix, int N, int M) {
int offset = '0' - 0;
char* inputTemp = (char*)malloc(sizeof(char) * (M + 1));
for (int i = 0; i < N; i++) {
scanf("%s", inputTemp);
for (int j = 0; j < M; j++)
matrix[i][j] = inputTemp[j] - offset;
}
free(inputTemp);
}
int isItSquare(int** matrix, int i, int j, int side) {
int val = matrix[i][j];
if (val == matrix[i][j + side - 1] && val == matrix[i + side - 1][j] && val == matrix[i + side - 1][j + side - 1])
return 1;
return 0;
}
int solve(int** matrix, int N, int M) {
int max = (N > M) ? N : M;
for (int side = max; side >= 2; side--) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (!(i + side - 1 < N && j + side - 1 < M))
continue;
else {
if (isItSquare(matrix, i, j, side))
return side;
}
}
}
}
return 1;
}
int main(void) {
int N, M; scanf("%d %d", &N, &M);
int** matrix = (int**)malloc(sizeof(int*) * N);
for (int i = 0; i < N; i++)
matrix[i] = (int*)malloc(sizeof(int) * M);
getMatrixInput(matrix, N, M);
int side = solve(matrix, N, M);
printf("%d", side * side);
for (int i = 0; i < N; i++)
free(matrix[i]);
free(matrix);
return 0;
}
'Problem Solving > Baekjoon Online Judge' 카테고리의 다른 글
[BOJ #5641] 겉보기에 쌍둥이 소수 (0) | 2020.08.04 |
---|---|
[BOJ #1629] 곱셈 (0) | 2020.08.02 |
[BOJ #1449] 수리공 항승 (0) | 2020.07.29 |
[BOJ #10816] 숫자 카드 2 (0) | 2020.07.27 |
[BOJ #13417] 카드 문자열 (0) | 2020.07.25 |
댓글