UVa 297 - Quadtrees

UVa 297 - Quadtrees

297 - Quadtrees

這題給了長長一大段敘述,簡的來說就是給你一串用前序表示的四元樹(Quadtrees),三個字母分別代表p: parent、f: full(塗黑區塊)、e: empty(白色區塊),若無子節點表示該區已塗滿(全黑或全白),反之(p)則繼續將該區塊切成四等分,每一string都代表一1024px的圖。要用程式讀取字串後算出有多少黑色pixels。對recursion不陌生做起來就不會很難,雖然題目叫Quadtrees但我並沒有建樹,而是直接無腦的用一個32x32(1024px)的空陣列記錄把黑pixels 填1白填0(預設全0)最後再一口氣count有幾個1 ,code如下:

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define DEBUG 0

using namespace std;

const int MAX_LENGTH=32;
string str;
int graph[MAX_LENGTH][MAX_LENGTH];

//s: string to solve, p: solving position, r: row, c: column, b: bound, pc: pixelCount
void drawBlack(const string str, int &p, int r, int c, int b)
{
	char ch = str.at(p++);	

	if(ch == 'p') //碰到p代表可以繼續切
	{
		drawBlack(str, p, r, c+b/2, b/2);
		drawBlack(str, p, r, c, b/2);
		drawBlack(str, p, r+b/2, c, b/2);
		drawBlack(str, p, r+b/2, c+b/2, b/2);
	}
	else if(ch == 'f') //碰到f代表可以把目前位置(r, c)加邊長b的pixels塗黑(填1)了
	{
		for(int i=r; i<(r+b); ++i)
			for(int j=c; j<(c+b); ++j)
				if(graph[i][j]==0)
					graph[i][j] = 1;
	}
}

int pixelCal()
{
	for(int i=0; i<MAX_LENGTH; i++)
		for(int j=0; j<MAX_LENGTH; j++)
			graph[i][j] = 0;
		
	int pixelCount=0;
	int p=0;
	
	cin >> str;
	drawBlack(str, p, 0, 0, MAX_LENGTH);
	
	p=0;
	
	cin >> str;
	drawBlack(str, p, 0, 0, MAX_LENGTH);
	
	for(int i=0; i<MAX_LENGTH; ++i)
		for(int j=0; j<MAX_LENGTH; ++j)
			if(graph[i][j])
				pixelCount++;
				
#if DEBUG == 1				
	for(int i=0; i<MAX_LENGTH; ++i)
	{
		for(int j=0; j<MAX_LENGTH; ++j)
			if(graph[i][j])
				cout << '#';
			else
				cout << ' ';
		cout << endl;
	}
#endif

	return pixelCount;
}

int main(int argc, char* argv[])
{
	int testTime=0;
	
	cin >> testTime;
	
	while(testTime--)
		cout << "There are " << pixelCal() << " black pixels." << endl;
	
	return 0;
}

Related Article