BOJ / 백준 / 1051 숫자 정사각형 C++

www.acmicpc.net/problem/1051

1051번: 숫자 정사각형

밤도 늦고 해서 그냥 쉬운 문제를 하나 풀어보았다. 얼른 자야겠다.

 

문제는 간단하다. 정답률이 왜 낮은지 잘 모르겠다. 아마 string으로 받아야되는데 띄어써서 input 해서 그런거 같다.

주어진 직사각형 숫자 판에서 가장 큰 정사각형의 크기를 구하는 것이다. 여기서 정사각형은 각 꼭지점의 수가 모두 일치하면 된다. 최대 크기는 50 x 50 이다.

 

전체 모든 경우를 다 돌아도 최대 2500 가지이고, 각 점마다 한 줄을 다시 최대 50번 탐색한다. 그리하여 같은 수가 나오면 그 길이만큼 계산하여 정사각형 모양이 되는 위치의 점들을 파악하면 된다. 50^3 이므로 주어진 시간 2초는 넉넉하다. 

 

코드는 다음과 같다.

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
	int n, m;
	int res = 1;
	char arr[50][50];

	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		string s;
		cin >> s;
		for (int j = 0; j < m; j++)
			arr[i][j] = s[j];
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++) {
			char c = arr[i][j];
			for (int k = 0; k < n; k++) {
				char tmp = arr[k][j];
				if (i == k)
					continue;
				if (c == tmp) {
					int dist = abs(i - k);
					if ((j + dist) >= 0 && (j + dist) < m) {
						if (tmp == arr[k][j + dist])
							if (c == arr[i][j + dist])
								res = max(res, (dist+1) * (dist+1));
					}
					if ((j - dist) >= 0 && (j - dist) < m) {
						if (tmp == arr[k][j - dist])
							if (c == arr[i][j - dist])
								res = max(res, (dist+1) * (dist+1));
					}
				}
			}
		}
	}

	cout << res;
}