23 人解决，25 人已尝试。
25 份提交通过，共有 45 份提交。
3.6 EMB 奖励。
2839. Reading a Quadtree
单点时限: 5.0 sec
内存限制: 256 MB
A quadtree, first introduced by Finkel and Bentley, is a tree data-structure in which each internal node has exactly four children. Quadtrees are often used for problems that can be mapped into a two-dimensional space which is then recursively subdivided it into four equally-sized regions while a certain condition holds. The problem consists in reading a compressed binary image represented with a quadtree and determining which pixels are
set to white.
For a better understanding of this problem, consider the third test case from Sample Input, represented in the figure. The uncompressed binary image is composed by (8 x 8) pixels, where 35 of them are white. Notice each node in the quadtree is mapped into a square area from the target image. White nodes denote areas composed by white pixels exclusively, whereas black nodes denote areas with only black pixels; finally, gray nodes are composed by white and black pixels and thus, they need to be subdivided into four new square areas. Notice that the order of visiting square areas is: left to right and top to bottom.
输入格式
The first line contains an integer N > 0 denoting the number of test cases.
The next N lines start each with the length L of the target image; L has to be a power of 2.
The length is followed by a space and a sequence of 0, 1 and *, denoting black, white and gray nodes of the quadtree, respectively. The quadtree is traversed in pre-order.
输出格式
The output consists of N lines containing each a comma-separated list of either:
a) (x,y) position of a pixel adjacent horizontally by black pixels, or
b) (xi-xf,y), where xf > xi: a sequence of white pixels at row y surrounded by black pixels.
The following holds: 1 <= x, xi, xf, y <= L. Traverse the binary image from left to right, top to bottom.
If L is not a power of 2, the output should display the text “Invalid length”, instead.
样例
Input
3 4 **1000*010010 7 *101*0100 8 *10*011*0010*1*101010
Output
(1,1),(4,1),(1-2,3),(1-2,4) Invalid length (1-4,1),(1-4,2),(1-4,3),(1-4,4),(3-7,5),(3-7,6),(1-2,7),(5-6,7),(1-3,8),(5-6,8)
题目标签