[1051번] 숫자 정사각형

www.acmicpc.net/problem/1051

1051번: 숫자 정사각형

 

N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오.

 

단순한 브루트포스 알고리즘 문제입니다. 완전탐색을 이용해 각 칸의 숫자를 확인하고 정사각형의 꼭짓점에 해당하는 칸을 탐색하여 4개의 수가 모두 같을 시에 가장 큰 정사각형의 길이를 +1 추가하는 방식으로 풀었습니다.

 

전체 소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int map[50][50]{};

int main() {
	int len = 1;
	int N, M;

	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		string input;
		cin >> input;

		for (int j = 0; j < M; j++) {
			map[i][j] = input[j] - '0';
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			for (int k = 1; k < min(N, M); k++) {
				if (i + k < N && j + k < M && map[i][j] == map[i][j + k] && map[i][j] == map[i + k][j] && map[i][j] == map[i + k][j + k]) {
					len = max(len, k + 1);
				}
			}
		}
	}
	int square = len * len;
	cout << square;
}