算法竞赛入门经典|算法竞赛入门经典 四分树
#include
#include
const int len = 32;
const int maxn = 1024 + 10;
char s[maxn];
int buf[len][len], cnt;
//把字符串s[p]导出到 以（r,c)为左上角，边长为w的缓存区里
//r,c默认为0，0；W默认为32
void draw(const char* s, int& p, int r, int c, int w) {
char ch = s[p++];
//s为字符串
// 21
// 34
if(ch == 'p') {//如果为中间节点
draw(s, p, r,c+w/2, w/2);
//1区域，s,p,横坐标r,纵坐标为，c+w/2
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(ch == 'f') { //涂黑
for(int i = r;
i < r+w;
i++)
for(int j = c;
j < c+w;
j++)
if(buf[i][j] == 0) { buf[i][j] = 1;
cnt++;
}//涂色并记录
}
}int main() {
int T;
scanf("%d", &T);
while(T--) {
memset(buf, 0, sizeof(buf));
cnt = 0;
for(int i = 0;
i < 2;
i++) {//把字符串输入进去
scanf("%s", s);
//用%s!
int p = 0;
draw(s, p, 0, 0, len);
//p为序号，r，c为0，0；len为长度
}
printf("There are %d black pixels.\n", cnt);
}
return 0;
}
/*
总结：
本题的精彩之处在于边涂色边记录；
思路为 先读入字符串，如果为中间节点递归画图，然后涂色记录；
*/ 【算法竞赛入门经典|算法竞赛入门经典 四分树】
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- typeScript入门基础介绍
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列
- 算法回顾（SVD在协同过滤推荐系统中的应用）