1051번: 숫자 정사각형

Memo

어려웠던 점

• 각 점에서 만족하는 정사각형을 찾는 것이 아닌, 정사각형 자체의 크기를 늘려가며 그 안에서 조건을 만족시키는 것을 파악하는 것. 다시 말해서, 문제를 해결하기 위한 주인공은 각 점이 아닌 정사각형 그 자체이다.

문제 평가

• 문제를 풀기 위해 먼저 "무식하게 풀어본다"에 초점을 맞춘 문제였다고 생각함. 즉 완전 탐색을 어떻게 적용할 지에 대한 고민이 충분히 필요했던 문제.

Code

제출 날짜

2021/03/03

메모리

2020KB

시간

0ms

#include <iostream>
#include <vector>

int N, M;
int ans;
std::vector<std::string> sq;

void input_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	input_faster();
	std::cin >> N >> M;
	sq.resize(N);
	for (size_t i = 0 ; i < N ; i++)
		std::cin >> sq[i];
	ans = 0;
}

int find_sq(int sq_size)
{
	for (int i = 0 ; i < N ; i++)
	{
		if (i + sq_size >= N)
			break;
		for (int j = 0 ; j < M ; j++)
		{
			if (j + sq_size >= M)
				break;
			if (sq[i][j] == sq[i + sq_size][j]&& sq[i][j] == sq[i][j + sq_size] && sq[i][j] == sq[i+sq_size][j+sq_size])
				return (1);
		}

	}
	return (0);
}

void solve()
{
	int i = 0;
	while (i <= N && i <= M)
	{
		if(find_sq(i))
			ans = (i + 1) * (i + 1);
		i++;
	}
}

void print_val()
{
	std::cout << ans;
}

int main()
{
	input();
	solve();
	print_val();
	return (0);
}