UVA297 思路+代码 还是递归~

题目链接

题目大意：
可以用一棵四分树来表示一副黑白像素，用根节点表示整幅图像，然后把行和列二等分，按照如下图中顺序编号为1—4，分别对应了四分数根节点从左往右的四个子节点，如果某子节点对应的区域为全黑或全白，则直接用一个黑节点或者白节点表示，如果既有黑节点又有白节点，那么就用一个灰节点表示，并且为这个区域递归建树。

输入两颗四分树的先序遍历序列，求二者合并（黑色部分合并）后的黑像素的个数，用p表示灰节点，f表示黑色，e表示白色，四分树的高度不超过5。

注： 默认图像的大小为 $32×32$32×32

解题思路：

递归：可以直接用一个二维数组表示一幅画板，然后将两颗四分树画在同一幅画板上， 最后计数整个画板上的黑色素的个数即可。

#include <iostream>
#include <cstring>
using namespace std;

const int Len = 32;
const int maxn = 4 << 6;

char s[maxn];
int board[Len][Len];	// 画板
int cnt;

void draw(const char *s,int &p,int r,int c,int w)	// 模拟画图
{		// 从画板 (r,c)开始画一个边长为w的图
	char tmp = s[p++];
	if(tmp=='p') {
		draw(s,p,r,c+w/2,w/2);	//区域1
		draw(s,p,r,c,w/2);		//区域2
		draw(s,p,r+w/2,c,w/2);	//区域3
		draw(s,p,r+w/2,c+w/2,w/2);	//区域4
	} else if(tmp=='f') {	// 画黑色像素格
		for(int i = r; i < r+w; ++i) 
			for(int j = c; j < c+w;++j) {
				if(!board[i][j]) {
					board[i][j] = 1;
					cnt++;	
				}
			}
	}
}
int main()
{
	int n;
	while(n--) {
		memset(0,board,sizeof(board));
		cnt = 0;
		for(int i = 0; i < 2; ++i) {
			cin >> s;
			int p = 0;
			draw(s,p,0,0,Len);
		}
		cout << "There are " << cnt << "black pixels.\n";
	}
}