Uva 297 Quadtrees

題目來源 ： https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=233


題意：如題目圖中所示，用一棵四分樹來表示一張黑白圖像，大小為32*32，所以總共有1024個pixels，如果子節點對應的區域為全黑或全白的話，可以用一個黑點(f)或一個白點(e)表示就可以了。

想法：這一題其實不用建樹，只要把兩張圖合併就可以了，所以一開始先建一個array[32][32]，並初始化為0，讀兩張圖進來，如果是黑點就塗黑(array[i][j] = 1)，白點不要理他，這樣最後就可以得到塗黑的pixel有幾個了。

塗黑的方法大概像下面那張圖，w是邊長，然後每個節點又可以分
成4個節點，所以是將一個圖四等分的感覺。

程式碼：

	#include<iostream>
	#include<cstring>
	#include<cstdio>
	#define total 1025
	#define edge 32
	using namespace std;
	char st[total];
	bool buffer[edge][edge];
	int counter;
	//p表示第幾個字母
	void draw(int& p,int r,int c,int w) {
	char ch = st[p++];
	if (ch == 'p') {
	draw(p, r, c, w / 2);
	draw(p, r, c + (w / 2), w / 2);
	draw(p, r + (w / 2), c, w / 2);
	draw(p, r + (w / 2), c + (w / 2), w / 2);
	}
	else if (ch == 'f') {
	for (int i = r; i < r + w; i++)
	for (int j = c; j < c + w; j++) {
	if (!buffer[i][j]) {
	buffer[i][j] = true;
	counter++;
	}
	}
	}
	}
	int main() {
	int N,p = 0;
	cin >> N;
	while (N--) {
	counter = 0;
	for (int i = 0; i < edge; i++)
	for (int j = 0; j < edge; j++)
	buffer[i][j] = false;
	for (int i = 0; i < 2; i++) {
	cin >> st;
	p = 0;
	draw(p, 0, 0, edge);
	}
	printf("There are %d black pixels.\n",counter);
	}
	system("PAUSE");
	}

view raw 297.cpp hosted with ❤ by GitHub