[백준][C++] 1051: 숫자 정사각형

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

 

배열에 직사각형을 다 집어넣고, 직사각형 각 칸마다 만들 수 있는 정사각형을 다 만들어서 가장 큰 정사각형을 저장하면 됩니다.

저는 각 칸마다 직사각형의 크기를 1x1, 2x2, 3x3 ... 이런식으로 키웠는데 생각해보니 거꾸로 하는게 더 효율적이겠네요. 귀찮아서 수정은 안하겠습니다

 

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING
#include <bits/stdc++.h>
using namespace std;


int n, m;
int rect[50][50];

inline bool in_range(int y, int x) {
	return y >= 0 && y < n && x >= 0 && x < m;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	cin >> n >> m;

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j) {
			char ch;
			cin >> ch;
			rect[i][j] = ch - '0';
		}

	int max_size = 1;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			// for each cell
			int cur_y = i, cur_x = j;
			while (in_range(cur_y, cur_x)) {
				if (rect[i][j] == rect[i][cur_x]
					&& rect[i][j] == rect[cur_y][j]
					&& rect[i][j] == rect[cur_y][cur_x])
					max_size = max(max_size, cur_y - i + 1);

				++cur_y, ++cur_x;
			}
		}
	}
	cout << max_size*max_size << '\n';

	return 0;
}

max_size는 한변의 길이입니다