【紫书】Quadtrees UVA - 297 四叉树涂色 - JavaScript

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：前序遍历给出两个像素方块。求两个方块叠加后有几个黑色格子。

题解：每次读进来一个方块，就在二维数组上涂色。每次把白色涂黑就cnt++；

具体递归方法是以右上角坐标与边长为参数，每次通过几何规律往下递归一层。

如果当前节点是'p'就继续递归,如果是f,e就说明是叶子结点，e直接返回,f对整个区域涂色。

#define _CRT_SECURE_NO_WARNINGS

#include "stdio.h"

#include<stdio.h>

#include<algorithm>

#include<string>

#include<vector>

#include<list>

#include<set>

#include<iostream>

#include<string.h>

#include<queue>

#include<string>

#include<sstream>

using namespace std;

const int maxn = +;

const int len = ;

char s[maxn];

int buf[len][len], cnt;

void draw(const char *s, int &p, int r, int c, int w) {

    char ch = s[p++];

    if (ch == 'p') {

        draw(s, p, r, c + w / , w / );

        draw(s, p, r, c, w / );

        draw(s, p, r + w / , c, w / );

        draw(s, p, r + w / , c + w / , w / );

    }else if(ch=='f')

        for(int i=r;i<r+w;i++)

            for(int j=c;j<c+w;j++)

                if (buf[i][j] == ) { buf[i][j] = ; cnt++; }

}

int main(){

    int t; cin >> t; while (t--) {

        memset(buf, , sizeof(buf));

        cnt = ;

        for (int i = ; i < ; i++) {

            scanf("%s", s);

            int p = ;

            draw(s, p, , , len);

        }

        printf("There are %d black pixels.\n", cnt);

    }

    return ;

}