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

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

1051번: 숫자 정사각형

풀이

---

가장 큰 정사각형의 크기를 구하면 되기 때문에 순회중인 타일의 위치를 (x, y)라고 하고 정사각형의 변의 길이를 i라고 하면 (x+i, y) (x, y+i) (x+i, y+i) 위치의 타일이 순회중인 타일의 번호가 같으면 넓이 비교를 하면 된다.

 

코드

---

#include <iostream>
#include <math.h>
using namespace std;
int map[100][100];
int flag[100][100][4];
int N, M;
bool inMap(int x, int y) {
	if (0 <= x && x < M && 0 <= y && y < N)
		return true;
	return false;
}

int main() {
	cin >> N >> M;
	for (int i = N-1; i >= 0; i--) {
		string str;
		cin >> str;
		for (int k = 0; k < M; k++) {
			map[i][k] = str[k] - '0';
		}
	}
	int maxArea = 1;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			int count = 1;
			int searchX = x + 1 * count;
			int searchY = y + 1 * count;
			while (inMap(searchX, searchY))
			{
				int searchTile = map[searchY][searchX];
				if (searchTile == map[y][x] && map[y][x] == map[y][searchX] && map[y][x] == map[searchY][x]) {
					if (searchX - x == searchY - y) {
						maxArea = max(maxArea, (searchX - x + 1) * (searchY - y + 1));
					}
				}
				count++;
				searchX = x + 1 * count;
				searchY = y + 1 * count;
			}
		}
	}
	cout << maxArea << endl;
}