Andrei Visalon (Prekzursil) Enunț
Se dă o matrice de rebus cu n linii și m coloane. Fiecare celulă conține unul dintre caracterele:
'+'– celulă blocată (nu poate conține literă)'-'– celulă liberă (trebuie completată cu o literă)
De asemenea, se dă o listă de W cuvinte (formate doar din litere mari A-Z) care trebuie completate în rebus.
Un cuvânt poate fi plasat:
- pe orizontală (în aceeași linie), sau
- pe verticală (în aceeași coloană),
într-un segment maximal de celule '-' consecutive (numit slot). Lungimea cuvântului trebuie să fie egală cu lungimea slotului.
Două cuvinte se pot intersecta (o celulă poate aparține atât unui slot orizontal, cât și unuia vertical), dar în acest caz litera rezultată în acea celulă trebuie să coincidă pentru ambele cuvinte.
Fiecare cuvânt din listă trebuie folosit exact o singură dată.
Cerința
Completați rebusul și afișați matricea finală.
Date de intrare
Fișierul de intrare "crossword.in" conține:
- pe prima linie numerele
nșim - pe următoarele
nlinii câte un șir demcaractere din mulțimea{'+', '-'}(fără spații) - pe ultima linie un șir care conține cele
Wcuvinte ce trebuie plasate, separate prin caracterul;.
Date de ieșire
Fișierul de ieșire "crossword.out" va conține n linii, fiecare cu m caractere, reprezentând rebusul completat (celulele '+' rămân neschimbate, iar celulele '-' devin litere mari A-Z).
Restricții și precizări
1 ≤ n, m ≤ 10001 ≤ W ≤ 200- fiecare cuvânt are lungimea între
2șimax(n, m) - cuvintele sunt formate doar din caractere
A-Z - se garantează că fiecare celulă
'-'aparține cel puțin unui slot (orizontal sau vertical) de lungime>= 2 - se garantează că numărul total de sloturi (orizontale + verticale) de lungime
>= 2este exactW - se garantează că există cel puțin o soluție și că soluția este unică
Exemplul 1
crossword.in
10 10 +-++++++++ +-++++++++ +-++++++++ +-----++++ +-+++-++++ +-+++-++++ +++++-++++ ++------++ +++++-++++ +++++-++++ LONDON;DELHI;ICELAND;ANKARA
crossword.out
+L++++++++ +O++++++++ +N++++++++ +DELHI++++ +O+++C++++ +N+++E++++ +++++L++++ ++ANKARA++ +++++N++++ +++++D++++
Exemplul 2
crossword.in
10 10 +-++++++++ +-++++++++ +-------++ +-++++++++ +-++++++++ +------+++ +-+++-++++ +++++-++++ +++++-++++ ++++++++++ AGRA;NORWAY;ENGLAND;GWALIOR
crossword.out
+E++++++++ +N++++++++ +GWALIOR++ +L++++++++ +A++++++++ +NORWAY+++ +D+++G++++ +++++R++++ +++++A++++ ++++++++++
Exemplul 3
crossword.in
10 10 ++++++-+++ ++------++ ++++++-+++ ++++++-+++ +++------+ ++++++-+-+ ++++++-+-+ ++++++++-+ ++++++++-+ ++++++++-+ ICELAND;MEXICO;PANAMA;ALMATY
crossword.out
++++++I+++ ++MEXICO++ ++++++E+++ ++++++L+++ +++PANAMA+ ++++++N+L+ ++++++D+M+ ++++++++A+ ++++++++T+ ++++++++Y+