백준 1992번 쿼드트리

www.acmicpc.net/problem/1992

 

 

 

 

<접근방법>

탐색하고 분할하고.

분할1을(를) 탐색하고

분할2을(를) 탐색하고

분할3을(를) 탐색하고

분할4을(를) 탐색하고

...

 

---

 

 

 

<코드>

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

#define MAX 64

int n;
int map[MAX][MAX];

string retZip(int y, int x, int size) {
	if (size == 1) {
		return to_string(map[y][x]);
	}

	bool zero = true, one = true;
	for (int i = y; i < y + size; i++) {
		for (int j = x; j < x + size; j++) {
			if (map[i][j]) {
				zero = false;
			}
			else {
				one = false;
			}
		}
	}

	string upLeft;
	string upRight;
	string downLeft;
	string downRight;


	if (zero) {
		return to_string(0);
	}
	else if (one) {
		return to_string(1);
	}
	else {
		upLeft = retZip(y, x, size / 2);
		upRight = retZip(y, x + size / 2, size / 2);
		downLeft = retZip(y + size / 2, x, size / 2);
		downRight = retZip(y + size / 2, x + size / 2, size / 2);
	}

	return "(" + upLeft + upRight + downLeft + downRight + ")";
}

int main() {
	cin >> n;

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

	cout << retZip(0, 0, n) << '\n';

	return 0;
}