Quad-trees P47304

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 $2^n \times 2^n$.

0.67 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 \le d \le n$, es refereix a un quadrat $2^{n-d} \times 2^{n-d}$.

0.3

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 \le n \le 8$.

Sortida

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