This page is still under construction.

Parts of this page are still being built. What you see may change.

Quadtrees

Time limit1sMemory limit128 MB

Summary
Given two quadtree preorder strings for 32x32 black-and-white images, count the black pixels in their union by recursively merging overlapping quadrants.
Level

Medium6 of 10

Topics
Recursion, Tree, Divide and conquer, Implementation
Solved
No attempts yet

Problem

A modern computer artist works with black-and-white images of 32 × 32 units, for a total of 1024 pixels per image. One of the operations the artist performs is adding two images together to form a new image. In the resulting image a pixel is black if it was black in at least one of the two source images; otherwise it is white.

A quadtree is a representation used to encode such images. The key idea is that any image can be split into four quadrants; each quadrant may again be split into four subquadrants, and so on. In the quadtree, the whole image is a parent node and its four quadrants are its four child nodes, listed in the fixed order shown below.

21
34

If a whole image (or quadrant) is a single color, it can be represented by a single node. In general, a quadrant needs to be subdivided only when it contains pixels of different colors, so the quadtree need not have uniform depth.

The preorder representation of a single-node quadtree is e if the node is an empty (white) quadrant, or f if the node is a full (black) quadrant. The preorder representation of a quadtree with more than one node is the letter p (for parent) followed by the preorder representations of its four subtrees, in the quadrant order shown above.

Given the quadtree representations of two images, write a program that computes the number of black pixels in the image obtained by adding them.

The figure below shows the first example (from top to bottom) as image, quadtree, preorder string, and number of pixels; the quadrant numbering is shown at the top of the figure.

Questions

  1. Give a preorder representation of the quadtree that encodes the image below.
  2. What are the lengths of the shortest and the longest possible strings representing the preorder traversal of a quadtree that encodes a 32 × 32 image? Explain your answer.
  3. Write a program that meets the specification below.

Input

The first line contains the number of test cases NN. Each test case is given on two lines, each holding one string. Each string is the preorder representation of a quadtree, and every string in the input is guaranteed to represent a valid quadtree.

Output

For each test case, print one line of the form There are X black pixels., where X is the number of black pixels in the image obtained by adding that test case's two images.

Examples1

  1. Example 1

    Input
    3
ppeeefpffeefe
pefepeefe
peeef
peefe
peeef
peepefefe
    Expected output
    There are 640 black pixels.
There are 512 black pixels.
There are 384 black pixels.