Uva--297 Quadtrees(非二叉树/四叉树)

记录
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);        
    }
}