Fişierul intrare/ieşire:	marceland.in, marceland.out	Sursă	Algoritmiada 2019 Runda PreOJI
Autor	Alexandru Petrescu	Adăugată de	Iordache Ioan-Bogdan •iordache.bogdan
Timp execuţie pe test	0.05 sec	Limită de memorie	524288 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

MarceLand

Dupa ce s-a clonat pe vaporul sau de mai multe ori, originalul Marcel a inceput sa-si priveasca clonele. Nu era greu sa iti dai seama care este cel original, pentru ca ceilalti Marcei erau haotici si lipsiti de initiativa. Dezamagit de proiect, Marcel voia sa ii lase pe acestia pe una din noile sale insule.

Insula poate fi vazuta de sus ca o matrice de dimensiuni N linii si M coloane, in care fiecare celula este fie o stanca (celula blocata, codificata prin caracterul #), fie o parcela libera. Intr-o parcela libera se poate afla fie casa unui Marcel (codificat prin litera / caracterul M), fie o fantana (codoficata prin @), fie nisip (codificata prin .). Prin dispunerea stancilor pe teren, insula poate fi un adevarat labirint pentru Marcei.

Marcel are acces la o celula a matricei daca se poate deplasa de la casa sa fie in sus, fie in jos, fie in stanga, fie in dreapta (cum ar privi Macel de sus, din elicopterul sau), doar prin parcele libere (caracterele '.', '@', 'M') pana la celula respectiva - cu alte cuvinte, daca exista un traseu 4-conex intre casa sa si celula respectiva care sa nu treaca prin stanci.

Desgiur ca fiecare Marcel nu vrea sa ramana dezhidratat, deci trebuie sa bea apa de la o fantana. Astfel, Macel vrea ca fiecare Marcel sa aiba acces la macar o fantana.

Cerinta

Dandu-se matricea care codifica insula, sa se adauge un numar cat mai mic de fantani, astfel incat fiecare Marcel sa poate ajunge, plecand de la casa sa, la macar o fantana. Pentru aceasta, se pot transforma cateva parcele de tip nisip (caracterul .) in parcele de tip fantana (caracterul @). Se cere o matrice care sa indeplineasca aceste conditii, sau sa se spuna ca nu se poate realiza acesta.

Date de intrare

Fişierul de intrare marceland.in contine, pe prima linie, numarul T de teste ce urmeaza sa fie descrise. Fiecare test are pe prima linie numerele N si M de linii si coloane a matricei, iar pe urmatoarele N linii cate M caractere din multimea {'.', '@', 'M', '#'}, descriind insula din testul respectiv.

Date de ieşire

În fişierul de ieşire marceland.out se vor afla T raspunsuri, pe rand, la fiecare test din input. Un raspuns este fie o linie cu numarul "-1", fie N + 1 linii, astfel: Prima linie contine numarul F, reprezentand numarul de fantani adaugate. Urmatoarele N linii se afla cate M caractere din multimea {'.', '@', 'M', '#'}, descriind insula dupa ce au fost adaugate F fantani.

Restricţii

• 1 ≤ T ≤ 5
• 1 ≤ N, M ≤ 100
• Pentru 30 de puncte, se garanteaza ca N = 1
• Pentru alte 30 de puncte, se garanteaza ca N = 2
• Pentru alte 10 de puncte, se garanteaza ca F = 0, adica nu e nevoie sa adaugam nicio fantana, pentru toate cele T teste din input pentru care exista solutie; pentru cele care nu exista, trebuie afisat "-1".
• Pentru alte 10 de puncte, se garanteaza ca, pentru toate cele T teste din input, exista solutie
• Se poate afisa orice solutie corecta
• Exista cel putin un Marcel pe insula
• Veţi primi rezultatele evaluării doar pe fişierul de intrare din exemplu. Acestea nu vor afecta scorul problemei, având punctajul asociat 0.

Exemplu

Cum se trimit solutii?