[BJ] 1992번 : 쿼드트리(재귀) / c++ & c / 제한시간 : 2초

www.acmicpc.net/problem/1992

1992번: 쿼드트리

 

<코드>

#pragma warning(disable:4996)
#include<stdio.h>
using namespace std;

char map[65][65];
int n, p = 0;
char ans[100000];

void compress(int x, int y, int edge) {
	char temp; 
	int i, j;
	temp = map[x][y];
	if (edge == 1) {
		if (temp == '1')ans[p++] = '1';
		else ans[p++] = '0';
		return;
	}

	for (i = x; i < x + edge; i++) {
		for (j = y; j < y + edge; j++) {
			if (temp != map[i][j]) {
				ans[p++] = '(';
				compress(x, y, edge / 2);
				compress(x, y + edge / 2, edge / 2);
				compress(x + edge / 2, y, edge / 2);
				compress(x + edge / 2, y + edge / 2, edge / 2);
				ans[p++] = ')';
				return;
			}
		}
	}
	if (temp == '1') ans[p++] = '1';
	else ans[p++] = '0';
	return;
}

int main() {
	int i;
	scanf("%d", &n);
	for (i = 0; i < n; i++)
			scanf("%s", &map[i]);

	compress(0, 0, n);
	for (i = 0; i < p; i++) {
		printf("%c", ans[i]);
	}
	puts("");
	return 0;
}