专栏首页ACM算法日常UVA297:黑白图像 Quadtrees(四分树)

UVA297:黑白图像 Quadtrees(四分树)

题目描述

四象树是每个内结点均有4个子结点的特殊四叉树,它可用于描述平面上黑白图像。平面上的黑白图像是32行×32列的正方形,每个格子称为1个象素,是最小的图像单位。正方形图像可分成四个相等的小正方形,可按直角坐标系四个象限的顺序分别编号1,2,3,4,分别对应于四象树的四个子结点。这样,32行×32列的图像就对应于一棵深度为6的完全四叉树,最底层的每个叶结点正好对应于一个象素。但我们可以压缩四象树的结点数量。

当图像上某个区域为全白或者全黑时,可把该区域在四象树上对应的结点描述为全白(用小写字母e表示)或者全黑(用小写字母f表示),并且对这样的结点不再扩展子结点,因为再扩展出的子树上每个结点都是相同的颜色。

只有当图像上某个区域为“杂色”时,才继续划分成四个子区域(在四象树上对应的结点用小写字母p表示),然后“纯”色的子区域也不再扩展,并继续扩展“杂”色子区域。例如,下图左、中两个图像可分别用它们下边的四象树描述。

我们感兴趣的问题是:当两个大小均为32*32的黑白图像叠加后,合成的新图像是什么样子。合成的规则是:当一个图像上某个区域为全黑时,新图像的这个区域即为全黑;当一个图像上某个区域为全白时,新图像的这个区域的颜色是另加一个图像上这个区域的颜色。上图准确地示例了本合成的规则。

我们给出两个图像对应四象树的先序遍历顺序,求合成后的图像中,黑色象素点的数量。

输入

多组测试数据,第1行一个整数T,表示测试数据的组数,每组数据的格式为:

第1行:一个字符串,描述第1棵四象树的先序序列

第2行:一个字符串,描述第2棵四旬树的先序序列

输出

对每组数据,在单独一行上输出一个整数,表示合成后的图像上黑色象素的数量,格式如输出样例所示:

样例输入

3
ppeeefpffeefe
pefepeefe
peeef
peefe
peeef
peepefefe

样例输出

There are 640 black pixels.
There are 512 black pixels.
There are 384 black pixels.

我直接把BZOJ的翻译粘过来了(逃

思路1:数据量很小。我第一次写时直接模拟了两棵四叉树的建树与搜索,然后捎带着把最后的黑色个数算出来了。其中黑色结点的值跟它的深度有关,写一写就能找到规律。

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

struct node
{
    char c;
    node *ptr[4];
    node(){for (int i = 0; i < 4; i++)    ptr[i] = NULL;}
};

node *root1, *root2;

int sum, cnt;//sum是最终结果,cnt是记录字符串走到哪个位置了

void release(node *root)//释放
{
    if (!root)    return;
    for (int i = 0; i < 4; i++)
        release(root->ptr[i]);
    delete root;
}

void build(string cur, node *&root)//建树,记得root要加地址符
{
    root = new node();
    root->c = cur[cnt++];
    if (root->c == 'p')
        for (int i = 0; i < 4; ++i)
        {
            root->ptr[i] = new node();
            build(cur, root->ptr[i]);
        }
}

void dfs(node *root1, node *root2, int depth)
{
    //大概分了三种情况讨论
    if (root1->c == 'f' || root2->c == 'f')//有一个是黑
    {
        sum += pow(4,6-depth);//数学可推……
        return;
    }
    else if (root1->c == 'e' && root2->c == 'e')//全是白
        return;
    //对于'p'的点深搜
    bool flag1 = root1->c=='p', flag2 = root2->c=='p';
    node *x = root1, *y = root2;
    for (int i = 0; i < 4; i++)
    {
        if (flag1)    x = root1->ptr[i];
        if (flag2)    y = root2->ptr[i];
        dfs(x, y, depth+1);
    }
}

int main()
{
    int test;
    scanf("%d", &test);

    while (test--)
    {
        sum = 0;
        string s,t;
        cin >> s >> t;
        cnt = 0, build(s, root1);
        cnt = 0, build(t, root2);

        dfs(root1, root2, 1);

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

        release(root1),release(root2);
    }

    return 0;
}

思路2:书上代码思路是在32*32的正方形里面涂色然后查找,貌似跟树也没什么关系了……书中的注释已经很明白了,见代码。(PS:UVA有毒)

#include <cstdio>
#include <cstring>

const int len = 32;
const int maxn = 1024 + 10;
//下面这个char数组和int变量定义顺序变一下UVA居然会WA啊!
//我从未见过如此厚颜无耻之OJ
char s[maxn];
int buf[len][len], cnt;

//把字符串s[p..]导出到以(r,c)为左上角,边长为w的缓冲区中
//2 1
//3 4
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/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 (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);
            int p = 0;
            draw(s, p, 0, 0, len);
        }

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

    }

    return 0;
}

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:AlphaWA

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-07-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 水果Fruit(母函数) - HDU 2152

    转眼到了收获的季节,由于有TT的专业指导,Lele获得了大丰收。特别是水果,Lele一共种了N种水果,有苹果,梨子,香蕉,西瓜……不但味道好吃,样子更是好看。 ...

    ACM算法日常
  • leetcode题解 | 78. 子集

    这个题目很容易想到使用DFS的方式来解决,因为组合的题容易产生转移方程,这样也是没有什么问题的。

    ACM算法日常
  • 力扣 526.优美的排序(next_permutation?)

    链接:https://leetcode-cn.com/problems/beautiful-arrangement

    ACM算法日常
  • Codeforces 977D 题解报告

    http://codeforces.com/contest/977/problem/D

    海天一树
  • BZOJ1509: [NOI2003]逃学的小孩(树的直径)

    第一行是两个整数N(3  N  200000)和M,分别表示居住点总数和街道总数。以下M行,每行给出一条街道的信息。第i+1行包含整数Ui、Vi、Ti(1...

    attack
  • P1601 A+B Problem(高精)

    题目背景 无 题目描述 高精度加法,x相当于a+b problem,[b][color=red]不用考虑负数[/color][/b] 输入输出格式 输入格式...

    attack
  • Day5下午解题报告1

    预计分数:100+60+30=190 实际分数:100+60+30=190 终于有一道无脑T1了哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈...

    attack
  • P2746 [USACO5.3]校园网Network of Schools

    题目描述 一些学校连入一个电脑网络。那些学校已订立了协议:每个学校都会给其它的一些学校分发软件(称作“接受学校”)。注意即使 B 在 A 学校的分发列表中, A...

    attack
  • Good Bye 2018 B. New Year and the Treasure Geolocation(思维)

    题目链接:http://codeforces.com/contest/1091/problem/B

    Ch_Zaqdt
  • 这绝对是C语言的一个经典例题了!

    意图很明显,要用swap函数中交换main函数中的a和b的值,但是很明显上述代码是达不到要求的,a和b的值没有发生改变。其实本题就是C中比较有名传址和传值的典型...

    7089bAt@PowerLi

扫码关注云+社区

领取腾讯云代金券