UVA297 四分树 Quadtrees TJ

题目链接

思路

模拟，按照紫书上的来，定义 (p) 传递着遍历字符串极为巧妙。
设置一个数组 (buf[1024][1024]) 用来存储图。
两个图合并就等于一张一张画在同一张图上，如果当前是白色就累加。
遇到 ('p') 就需要将边长除以二，分四种情况分类讨论。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int LEN = 32;
const int MAXN = 1024 + 10;
char s1[MAXN];
int T ,ans ,buf[LEN + 1][LEN + 1];//画到buf上 
void draw (char *s ,int &p ,int r ,int c ,int len) {
	char ch = s[p ++];
	if (ch == 'p') {
		draw (s ,p ,r ,c + len / 2 ,len / 2);//顺序不要搞错
		draw (s ,p ,r ,c ,len / 2);
		draw (s ,p ,r + len / 2 ,c ,len / 2);
		draw (s ,p ,r + len / 2 ,c + len / 2 ,len / 2);
	}
	else if (ch == 'f') {
		for (int q = r;q < r + len;++ q) {
			for (int w = c;w < c + len;++ w) {
				if (buf[q][w] == 0) { buf[q][w] = 1; ans ++; }
			}
		}
	}
}
int main () {
	scanf ("%d",&T);
	while (T --) {
		memset (buf ,0 ,sizeof (buf));
		ans = 0;
		for (int q = 0;q < 2;++ q) {
			scanf ("%s",s1);
			int p = 0;
			draw (s1 ,p ,1 ,1 ,LEN);
		}
		printf ("There are %d black pixels.
",ans);
	}
	return 0;
}