Problem 1214: joc

Pe o tablă pătrată de dimensiune $n \cdot n$ se desenează o secvenţă de triunghiuri dreptunghic isoscele.

Fiecare triunghi are vârfurile numerotate cu $1, 2$ şi $3$ ( $2$ corespunde unghiului drept iar ordinea $1, 2, 3$ a vârfurilor este în sens invers acelor de ceasornic – vezi figura).

Triunghiurile au catetele paralele cu marginile tablei. Primul triunghi, având lungimea catetei $Lg$ , are vârful $1$ pe linia $L$ şi coloana $C$ şi este orientat ca în figură.
Jocul constă în alipirea câte unui nou triunghi la unul din vârfurile $2$ sau $3$ ale triunghiului curent. Dacă se alătură colţului $2$ , noul triunghi se aşează cu vârful $1$ în prelungirea laturii $[1,2]$ a triunghiului curent, iar dacă se alătură colţului $3$ se aşează cu vârful $1$ în prelungirea laturii $[2,3]$ .

Iniţial noul triunghi este orientat ca şi cel anterior. El se poate plasa pe tablă dacă nu sunt depăşite marginile acesteia sau nu se suprapune peste un alt triunghi. În caz contrar, se face o singură rotaţie cu ${90\degree}$ spre stânga, obţinându-se o nouă orientare a triunghiului. Dacă nici în acest caz noul triunghi nu poate fi plasat, jocul se opreşte.

Zona ocupată de primul triunghi se completeză cu litera a; zona celui de-al doilea se completeză cu litera b, ş.a.m.d. Când literele mici ale alfabetului englez sunt epuizate, se reîncepe de la a.

Cerință

Cunoscându-se dimensiunea tablei, poziţia primului triunghi (linie, coloană) şi lungimea catetei precum şi o secvenţă de triunghiuri care se doresc a fi alipite se cere să se genereze matricea rezultată în finalul jocului.

Jocul se termină dacă un triunghi nu mai poate fi alipit sau au fost plasate toate triunghiurile descrise în secvenţă.

Date de intrare

În fişierul de intrare joc.in, pe prima linie se află $n$ (dimensiunea tablei). Pe a doua linie separate prin câte un spaţiu se află: $L$ (linia), $C$ (coloana) şi $Lg$ (lungimea catetei) corespunzătoare primului triunghi. Următoarele linii, până la sfârşitul fişierului, conţin câte două numere naturale separate prin câte un singur spaţiu reprezentând colţul triunghiului curent la care va fi alipit triunghiul următor şi dimensiunea catetei triunghiului următor.

Date de ieșire

În fişierul de ieşire joc.out va fi afişată matricea rezultată. Celulele tablei care nu sunt completate cu litere ale alfabetului vor fi completate cu ..

Restricții și precizări

$1 \leq n \leq 100$
$1 \leq C, L \leq n$
$2 \leq Lg \leq n$
Fiecare linie din fişierul de intrare şi din fişierul de ieşire se termină cu marcaj de sfârşit de linie

Exemplu

joc.in

joc.out

....................
....................
..........fffffeee..
..........ffff..ee..
..........fff....e..
..........ff..dddd..
..........f....ddd..
......hhggg...b.dd..
......h.gg...bb..d..
jjjiiii.g...bbb..c..
jj.iii.....bbbb.cc..
j..ii.....bbbbbccc..
k..i......a.........
kk.......aa.........
kkkl....aaa.........
...llm.aaaa.........
.....mm.............
.....mmmn...........
........nn..........
........nnn.........

Explicație

Triunghiul a este plasat în linia $16$ coloana $8$ şi are latura $4$ .

Triunghiul b se alipeşte în colţul $3$ şi are lungimea $5$ .

Triunghiul c se alipeşte în colţul $2$ şi are lungimea $3$ . Tringhiurile a, b şi c păstrează aceeaşi aranjare.

Triunghiul d nu se poate alipi în aceeaşi aranjare colţului $3$ deoarece are cateta de lungimea $4$ şi depăşeşte tabla. Rotim triunghiul cu ${90^{ \large \circ }}$ spre stânga şi obţinem o nouă aranjare.

Triunghiul e se alipeşte în colţul $2$ şi are cateta de lungime $3$ în aranjarea curentă.

Triunghiul f nu se poate alipi în aceeaşi aranjare cu e în colţul $3$ deoarece are cateta de lungimea $5$ şi depăşeşte tabla. Rotim triunghiul cu ${90^{ \large \circ }}$ spre stânga şi obţinem o nouă aranjare.

Triunghiul f se alipeşte în colţul $3$ , are lungimea $5$ şi o nouă aranjare.

Algoritmul continuă până la al $14$ -lea triunghi, n. Al $15$ -lea triunghi nu se mai poate plasa.

joc