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)

22 人解决,24 人已尝试。

24 份提交通过,共有 43 份提交。

3.6 EMB 奖励。

创建: 9 年,10 月前.

修改: 2 年,11 月前.

最后提交: 8 年,9 月前.

来源: Mexico 2010

题目标签