记录
18:34 2023-5-20
uva.onlinejudge.org/external/2/297.html
reference:《算法竞赛入门经典第二版》例题6-11
非二叉树，这还是比较有趣的，图形学上还有八叉树用来划分空间的。
这道题将图和四叉巧妙的结合起来，其原理也是使用先序遍历，边读边建树
#include<cstdio>
#include<cstring>
#define MAX_N 1024
using namespace std;
typedef long long ll;
typedef unsigned int uint;
const int INF = 0x3f3f3f3f;
const int len = 32;
char s[MAX_N];
int buf[len][len];
int result = 0;
//以(r, c)为左上角， w为此时方块长度
void solve(const char*s, int &p , int r, int c, int w) {
char t = s[p++];
if(t == 'p') {
solve(s, p, r, c + w / 2, w / 2); // 1
solve(s, p, r, c, w / 2); // 2
solve(s, p, r + w / 2, c, w / 2); // 3
solve(s, p, r + w / 2, c + w / 2, w / 2 ); // 4
} else if (t == '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;
result += 1;
}
}
}
} else {
//empty 不用进行处理
}
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
memset(buf, 0, sizeof(buf));
result = 0;
for(int i = 0; i < 2; i++) {
scanf("%s", s);
int p = 0;
solve(s, p, 0, 0, len);
}
printf("There are %d black pixels.\n", result);
}
}