Arbres fractals P99327

Statement

Sigui $p$ un nombre natural, i sigui $n = 2^{p+1} - 1$ . Considereu un tauler $n \times n$ ple de punts. Començant a la cantonada superior esquerra, feu $2^p$ passos baixant en diagonal, marcant amb ‘X’ les caselles per les quals passeu. Des del punt final, feu $2^{p-1}$ passos en els dos sentits perpendiculars a la direcció que portàveu (en aquest cas, amunt a la dreta i avall a l’esquerra). Des de cadascun dels dos punts finals, feu $2^{p-2}$ passos en els dos sentits perpendiculars a la direcció que portàveu, etc. Aquest procés acaba quan només es fa un pas.

En l’exemple d’entrada 1 podeu veure el resultat amb $p = 3$ .

Feu un programa que escrigui el resultat d’aquest procés recursiu, però podent començar a qualsevol de les quatre cantonades.

Entrada

L’entrada consisteix en un natural $p$ seguit d’una paraula que indica la posició des d’on es comença: “DE” (a dalt a l’esquerra), “DD” (a dalt a la dreta), “BE” (a baix a l’esquerra), o “BD” (a baix a la dreta).

Sortida

Escriviu $n$ línies amb $n$ caràcters cadascuna, amb el resultat del procés explicat anteriorment.

Public test cases

Input

3 DE

Output

X.........X....
.X.......X.....
..X.....X.X....
...X.......X...
....X.....X.X.X
.....X...X...X.
......X.X...X..
.......X.......
..X...X........
.X...X.........
X.X.X..........
...X...........
....X.X........
.....X.........
....X..........

Input

2 BE

Output

..X....
.X.....
X.X....
...X...
..X.X.X
.X...X.
X...X..

Input

0 DD

Output

Input

4 BD

Output

....................X..........
.....................X.........
....................X.X........
...................X...........
................X.X.X..........
.................X...X.........
..................X...X........
.......................X.......
......................X.X...X..
.....................X...X...X.
....................X.....X.X.X
...................X.......X...
..................X.....X.X....
.................X.......X.....
................X.........X....
...............X...............
....X.........X.X..............
.....X.......X...X.............
....X.X.....X.....X............
...X.......X.......X...........
X.X.X.....X.........X..........
.X...X...X...........X.........
..X...X.X.............X........
.......X...............X.......
........X...X...........X......
.........X...X...........X.....
..........X.X.X...........X....
...........X...............X...
........X.X.................X..
.........X...................X.
..........X...................X

Information

Author: Salvador Roura
Language: Catalan
Official solutions: C++
User solutions: C++