[백준] 1051-숫자 정사각형(C++)

문제링크: https://www.acmicpc.net/problem/1051

1051번: 숫자 정사각형

 

브루트포스 문제입니다. 모든 점에서 꼭짓점값들을 확인해서 가장크게 만들 수 있는 정사각형 넓이를 출력하는 문제였습니다. 정답률이 30퍼때라 좀 어려울 줄 알았는데 생각보다 너무 쉬워서 놀랐습니다.

 

각 점에서 오른쪽과 아래로 내려갈 수 있는 값들을 고려하면서 값을 도출합니다.

 

코드가 너무 쉬워서 설명은 생략하겠습니다. :)

아래는 정답코드입니다. 

#include <iostream>
#include <string>
using namespace std;

int n, m, result = 1;
int arr[51][51] = { 0 };
string input;

int main() {

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
			cin >> input;
			for (int j = 0; j < input.size(); j++)
				arr[i][j] = input[j] - '0';
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int cnt = 0;
			for (int k = 1;; k++) {
				if ((j + k) >= m || (i + k) >= n) break;
				if (arr[i][j] == arr[i][j + k] && arr[i][j] == arr[i + k][j] && arr[i][j] == arr[i + k][j + k])
					if(cnt < k)
						cnt = k;
			}
			if ((cnt + 1) > result) result = cnt + 1;
		}

	}

	cout << result * result << endl;
}