[백준] 1051번 숫자 정사각형

https://www.acmicpc.net/problem/1051

1051번: 숫자 정사각형

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

int main() {
	cin.tie(NULL);
	int n, m;
	cin >> n >> m;
	vector<vector<int>> v(n, vector<int>(m));
	int length = min(n, m) - 1;
	string s;
	for (int i = 0; i < n; i++) {
		cin >> s;
		for (int j = 0; j < m; j++) {
			v[i][j] = stoi(s.substr(j, 1));
		}
	}
	bool flag = false;
	while (true) {
		for (int row = 0; row + length < n; row++) {
			for (int col = 0; col + length < m; col++) {
				if (v[row][col] == v[row + length][col] && v[row][col] == v[row][col + length] && v[row][col] == v[row + length][col + length]) {
					flag = true;
					break;
				}
			}
			if (flag)
				break;
		}
		if (flag) break;
		length--;
	
	}
	cout << (length + 1) *(length + 1);
	return 0;
}

네모칸을 점점 줄여가면서 이동시키면서 네 꼭짓점의 값이 같은 정사각형을 발견해나가면 된다.

변의 길이는 가로, 세로의 길이 중 짧은 것으로 시작한다. (그것을 length로 뒀다)

기준이 되는 점인 (row, col)을 왼쪽에서 오른쪽으로, 위에서 아래로 옮겨가면서 네 칸의 값이 같을 때까지 반복한다.

끝까지 갔는데 발견되지 않으면 length를 줄이고 그것을 반복한다.

주의할 점은 변의 길이가 3이면 세 칸을 차지하는 것이니까 0~3이 아니라 0~2라는 것이다. 따라서 변의 길이가 3이면 length를 2가 되게 했다. row + length 했을 때 두 칸을 더해야 되니까. 그리고나서 나중에 크기를 구할 때에는 length에 1을 더해주었다.