Misopan şi Trofonaced sunt doi eroi care vor să-şi unească forţele în lupta împotriva răului. Regatul este reprezentat printr-o matrice dreptunghiulară de N linii şi M coloane. Fiecare element al matricei corespunde unei bucăţi de teren uscat sau mlăştinos. Cei doi eroi nu se vor aventura în părţile mlăştinoase ale regatului – se vor deplasa numai pe uscat. Ei se pot muta dintr-o poziţie a matricei în una din cele 4 poziţii vecine pe orizontală sau pe verticală, dacă această poziţie corespunde unei zone de uscat. Unele poziţii de uscat pot fi transformate prin vrajă în mlaştină.
Cerinţă
Ajutaţi un vrăjitor malefic să aleagă un număr minim de poziţii ”transformabile“, prin schimbarea cărora cei doi eroi să nu se poată întâlni (să nu existe un drum pe uscat între cei doi).
Date de intrare
Prima linie a fişierului magic5.in conţine două numere întregi N şi M reprezentând numărul de linii, respectiv de coloane ale matricei. Următoarele N linii conţin câte M caractere cu următoarea semnificaţie: . pentru o poziţie uscată x (mic) pentru una mlăştinoasă * pentru una uscată ”transformabilă“ în una mlăştinoasă de către vrăjitor M pentru poziţia eroului Misopan T pentru poziţia eroului Trofonaced
Date de ieşire
Pe prima linie a fişierului magic5.out se scrie numărul întreg R, reprezentând numărul minim de poziţii care trebuie transformate. Pe următoarele R linii vor apărea câte 2 numere, reprezentând poziţiile alese. Primul număr va fi linia (între 1 şi N), iar al doilea va fi coloana (între 1 şi M).
Restricţii
1 <= N, M <= 50 R (rezultatul afişat) poate fi 0
Pe testele date va exista întotdeauna soluţie
Se garantează că în toată matricea caracterele M, respectiv T vor apărea fiecare exact o dată
Poziţiile eroilor sunt implicit zone de uscat care nu pot fi transformate de vrăjitor