Multi
copii sunt familiarizati cu un joc in care o biluta este plasata intr-o cutie
patrata in care sunt diferite obstacole, astfel incat interiorul cutiei are
aspectul unui labirint. Tinand cutia vertical, bila poate cadea (sub influenta
gravitatiei) pana la marginea cutiei sau pana la intalnirea unui obstacol.
Cutia poate
fi rotita cu 90 de grade (in sensul acelor de ceas sau invers). Ca urmare, sub
influenta gravitatiei, din nou bila se va deplasa pana la intalnirea unui obstacol
sau a marginilor cutiei.
Cutia
jocului poate fi reprezentata ca o matrice cu N
linii si N coloane. Daca elementul
de pe linia i si coloana j
este un obstacol el va fi marcat in matrice cu litera X,
iar daca este culoar, va fi marcat in matrice cu .
(punct). Pozitia bilei va fi marcata in matrice cu litera B.
Cerinta
Scrieti un program care sa determine configuratia cutiei dupa o secventa de
rotatii specificata.
Date
de intrare
Fisierul de intrare cutie.in
contine pe prima linie doua numere naturale separate prin spatiu
N K, unde N reprezinta
dimensiunea cutiei, iar K reprezinta
numarul de rotatii. Pe urmatoarele N
linii sunt scrise cate N caractere,
reprezentand configuratia initiala a cutiei. Pe urmatoarele K
linii sunt scrise rotatiile, cate o rotatie pe o linie. O rotatie este descrisa
prin litera S daca rotatia se
face cu 90 de grade in sensul invers acelor de ceas, sau prin litera D
daca rotatia se realizeaza cu 90 de grade in sensul acelor de ceas.
Date de
iesire
Fisierul de iesire cutie.out
va contine N linii, fiecare linie
continand exact N caractere,
reprezentand configuratia cutiei dupa executarea celor K
rotatii.
Restrictii
1 <= N <= 1000
1 <= K <= 500 000
Exemplu
cutie.in
cutie.out
cutie.in
cutie.out
6 2
....XX
X.....
......
..B...
.XXX..
......
S
D
....XX
X.....
......
......
.XXX..
B.....
10
7
..........
XXXXXXXXX.
..X.....X.
..X.....X.
........X.
........X.
...X....X.
...X....X.
.XXXXXXXX.
B.........
S
S
S
S
D
D
S
