치노의 라떼 아트 (Easy) (feat. 백준, 27311번)

치노의 라떼 아트 (Easy)
https://www.acmicpc.net/problem/27311

27311번: 치노의 라떼 아트 (Easy)

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    ios::sync_with_stdio(false), cin.tie(NULL);
    register int T;
	cin >> T;
	for (register int t = 0; t < T; ++t) {
		char arr[10][10];
		register int N, M;
		cin >> N >> M;
		// 큰 사각형 경계 찾기
		int totalCream = 0, msquare = 0, nsquare = 0;
		int min_x = 11, min_y = 11, max_x = -11, max_y = -11, first_x = -1, first_y = -1;
		for (register int i = 0, j; i < N; ++i) {
			for (j = 0; j < M; ++j) {
				cin >> arr[i][j];
				if (arr[i][j] == '#') {
					++totalCream;
					if (first_x == -1)
						first_x = i, first_y = j;
					min_x = min(min_x, i);
					min_y = min(min_y, j);
					max_x = max(max_x, i);
					max_y = max(max_y, j);
				}
			}
		}
		// 만약 #이 없으면 하트가 안됨
		if (first_x == -1 && first_y == -1) {
			cout << "0" << "\n";
			continue;
		}
		msquare = max_x - min_x + 1;
		//정사각형 모양이 아니면 하트가 안됨
		if (max_y - min_y + 1 != msquare) {
			cout << "0" << "\n";
			continue;
		}
		//작은 사각형 경계 찾기
		register int m_cream = 0, n_cream = 0;
		register int min_nx = 11, min_ny = 11, max_nx = -11, max_ny = -11, first_nx = -1, first_ny = -1;
		for (register int i = min_x, j; i <= max_x; ++i) {
			for (j = min_y; j <= max_y; ++j) {
				if (arr[i][j] == '#')
                    ++m_cream;
				else {
					if (first_nx == -1)
						first_nx = i, first_ny = j;
					min_nx = min(min_nx, i);
					min_ny = min(min_ny, j);
					max_nx = max(max_nx, i);
					max_ny = max(max_ny, j);
					++n_cream;
				}
			}
		}
		//. 이 없으면 하트가 안됨
		if (first_nx == -1 && first_ny == -1) {
			cout << "0" << "\n";
			continue;
		}
		// 모서리에 작은 사각형 경계가 없으면 하트가 안됨
		if (!((min_nx == min_x && min_ny == min_y) || (min_nx == min_x && max_ny == max_y) || (max_nx == max_x && min_ny == min_y) || (max_nx == max_x && max_ny == max_y)) ) {
			cout << "0" << "\n";
			continue;
		}
		nsquare = max_nx - min_nx + 1;
		//작은 사각형이 정사각형 모양이 아니면 하트가 안됨
		if (max_ny - min_ny + 1 != nsquare) {
			cout << "0" << "\n";
			continue;
		}
		// 작은사각형 안에 #이 섞여있으면 하트가 안됨
		if (totalCream != msquare * msquare - nsquare * nsquare) {
			cout << "0" << "\n";
			continue;
		}
		cout << "1" << "\n";
	}
	return 0;
}
// *&)*@*

 

반응형

문제의 요구사항에 따라 풀이하면 됩니다.

처음엔 bfs 유형이라고 생각했는데 그냥 구현 문제였네요.