【例题 6-11 UVA-297】Quadtrees

【链接】 我是链接,点我呀:)

【题意】

在这里输入题意

【题解】

发现根本不用存节点信息。
遇到了叶子节点且为黑色,就直接覆盖矩阵就好(因为是并集);

【代码】

#include <bits/stdc++.h>

using namespace std;

const int N = (1 << 5) + 10;

string s;

int pos, bo[N][N];

void fugai(int x1, int y1, int x2, int y2) {

	for (int i = x1; i <= x2; i++)

		for (int j = y1; j <= y2; j++)

			bo[i][j] = 1;

}

void dfs(int x1, int y1, int x2, int y2) {

	if (s[pos] == 'f' || s[pos] == 'e') {

		if (s[pos] == 'f') {

			fugai(x1, y1, x2, y2);

		}

		return;

	}

	int len = (x2 - x1 + 1) / 2;

	pos++;

	dfs(x1, y1 + len, x1 + len - 1, y1 + len + len - 1);

	pos++;

	dfs(x1, y1, x1 + len - 1, y1 + len - 1);

	pos++;

	dfs(x1 + len, y1, x1 + len + len - 1, y1 + len - 1);

	pos++;

	dfs(x1 + len, y1 + len, x1 + len + len - 1, y1 + len + len - 1);

}

int main() {

	//freopen("rush.txt", "r", stdin);

	int T;

	scanf("%d", &T);

	while (T--) {

		memset(bo, 0, sizeof bo);

		cin >> s;

		pos = 0;

		dfs(1, 1, 32, 32);

		cin >> s;

		pos = 0;

		dfs(1, 1, 32, 32);

		int cnt = 0;

		for (int i = 1; i <= 32; i++)

			for (int j = 1; j <= 32; j++)

				cnt += bo[i][j];

		printf("There are %d black pixels.\n", cnt);

	}

	return 0;

}