Quad-trees P47304


Statement
 

pdf   zip

html

Un quad-tree és una codificació d’imatges dos-dimensionals de la manera recursiva següent: Un quad-tree de nivell 0 és un píxel (un quadradet) blanc o negre. Un quad-tree de nivell n > 0 consisteix en 4 quad-trees de nivell n − 1, cadascun dels quals codifica un quart de la imatge: el quart de dalt a l’esquerra, el de dalt a la dreta, el de baix a l’esquerra, i el de baix a la dreta, numerats entre 0 i 3 en aquest ordre. Un quad-tree de nivell n té mida 2n × 2n.

Per exemple, a la dreta tenim un quad-tree de nivell n = 3. Dels 64 píxels, 9 són negres i la resta són blancs. L’estructura recursiva dels quad-trees ens permet referir-nos a diversos quadrats amb strings de {‘0’, ‘1’, ‘2’, ‘3’}. Per exemple, “2” es refereix al quadrat pintat de verd (el de baix a l’esquerra), “13” es refereix al pintat de vermell (del quadrat de dalt a la dreta ‘1’, n’és el sub-quadrat de baix a la dreta ‘3’), i “330” es refereix al pintat de blau. Fixeu-vos que un string amb d dígits, amb 0 ≤ d ≤ n, es refereix a un quadrat 2n−d × 2n−d.
unit=0.25cm (20,19) (3,1)0 (5,1)1 (7,1)2 (9,1)3 (11,1)4 (13,1)5 (15,1)6 (17,1)7 (1,3)7 (1,5)6 (1,7)5 (1,9)4 (1,11)3 (1,13)2 (1,15)1 (1,17)0 linestyle=solid linecolor=black -(2,2)(18,2) -(2,4)(18,4) -(2,6)(18,6) -(2,8)(18,8) -(2,10)(18,10) -(2,12)(18,12) -(2,14)(18,14) -(2,16)(18,16) -(2,18)(18,18) -(2,2)(2,18) -(4,2)(4,18) -(6,2)(6,18) -(8,2)(8,18) -(10,2)(10,18) -(12,2)(12,18) -(14,2)(14,18) -(16,2)(16,18) -(18,2)(18,18) (4,14)(6,16) (4,8)(6,10) (8,12)(10,16) (14,16)(16,18) (14,10)(16,12) (6,4)(12,6) [hatchcolor=green,fillstyle=crosshatch,hatchsep=0.4](2,2)(10,10) [hatchcolor=red,fillstyle=crosshatch,hatchsep=0.4](14,10)(18,14) [hatchcolor=blue,fillstyle=crosshatch,hatchsep=0.4](14,4)(16,6)

Feu un programa que pinti quadrats d’un quad-tree inicialment tot blanc, i que n’escrigui el contingut. L’ordre per escriure és “PRINT”. Cada ordre per pintar es codifica amb un string tal i com s’ha explicat anteriorment, acabat amb ‘b’ o ‘n’. Aquest últim caràcter indica si cal pintar de blanc (amb un punt) o de negre (amb ‘X’).

Entrada

L’entrada consisteix en diversos casos, cadascun amb n seguida de diverses ordres correctes. L’ordre per parar cada cas és “STOP”. Poseu suposar 0 ≤ n ≤ 8.

Sortida

Per a cada ordre “PRINT”, escriviu la imatge actual, seguida d’una línia amb 10 guions.

Public test cases

  • Input

    3
PRINT
13n
PRINT
2n
230b
PRINT
STOP

1
n
PRINT
0n
PRINT
STOP

0
PRINT
STOP

    Output

    ........
........
........
........
........
........
........
........
----------
........
........
......XX
......XX
........
........
........
........
----------
........
........
......XX
......XX
XXXX....
XXXX....
XX.X....
XXXX....
----------
XX
XX
----------
XX
XX
----------
.
----------
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++