백준 6576번 쿼드 트리 C++

출처 : https://www.acmicpc.net/problem/6576

 

분할 정복으로 n * n 의 픽셀을 구하고 그것을 16진수로 출력하는 문제이다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

string str;
int idx = 0;

void rec(vector<vector<char>>& board, int row, int col, int n) {
	if (idx >= str.length()) return;
	if (str[idx] == 'Q') {
		idx++;
		rec(board, row, col, n / 2);
		rec(board, row, col + n / 2, n / 2);
		rec(board, row + n / 2, col, n / 2);
		rec(board, row + n / 2, col + n / 2, n / 2);
	}
	else {
		for (int i = row; i < row + n; i++) {
			for (int j = col; j < col + n; j++) {
				board[i][j] = str[idx];
			}
		}
		idx++;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;
	vector<vector<char>> board(n, vector<char>(n));
	cin >> str;
	rec(board, 0, 0, n);
	vector<vector<int>> ans(n, vector<int>(n / 8, 0));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n / 8; j++) {
			for (int k = j * 8; k < j * 8 + 8; k++) {
				if (board[i][k] == 'B') ans[i][j] += pow(2, k - (j * 8));
			}
		}
	}

	cout << "#define quadtree_width " << n << "\n";
	cout << "#define quadtree_height " << n << "\n";
	cout << "static char quadtree_bits[] = {" << "\n";
	for (auto a : ans) {
		for (auto b : a) {
			if (b <= 15) {
				cout << "0x0" << hex << b << ",";
			}
			else {
				cout << "0x" << hex << b << ",";
			}
		}
		cout << "\n";
	}
	cout << "};";
};