Eşti inginer la o firmă care construieşte circuite integrate şi proiectezi un nou circuit integrat pe o plăcuţă de (N+2)x(M+2) milimetri. Pe plăcuţă este trasat un caroiaj care împarte plăcuţa în (N+2)x(M+2) celule cu latura de 1 mm. Celulele sunt organizate în N+2 linii (numerotate de sus in jos de la 0 la N+1) şi M+2 coloane (numerotate de la stanga la dreapta de la 0 la M+1). O celulă este identificată prin numărul liniei şi numărul coloanei pe care se află.
Celulele situate pe linia 0, linia N+1, coloana 0 şi coloana M+1 constituie bordura plăcuţei.
Unele celule de pe plăcuţă conţin o componentă electronică. Pe bordură nu se află componente electornice.
Două componente electronice pot fi conectate dacă se poate determina un traseu între cele două componente, format numai din segmente verticale şi segmente orizontale, traseu care nu intersectează alte componente electronice. Este posibil ca o parte a traseului să fie pe bordură.
De exemplu:

Componentele situate în celulele de coordonate (3,1) şi (4,4) pot fi conectate. De asemenea, componentele situate în celulele (3,2) şi (3,5) pot fi conectate. Dar componente din celulele (3,2) şi (4,3) nu pot fi conectate.
Orice traseu începe şi se sfârşeşte în centrul unei celule şi trece prin centrul celulelor traversate.

Cerinţă

Scrieţi un program care să determine pentru fiecare pereche de componente dintr-un set dat dacă acestea pot fi sau nu conectate şi dacă da, care este lungimea minimă a unui traseu care permite conectarea componentelor.

Date de intrare

Fişierul de intrare inginer.in conţine pe prima linie numerele naturale N şi M, separate prin spaţiu. Pe următoarele N linii este descrisă plăcuţa (exceptând bordura); pe fiecare dintre aceste linii sunt scrise câte M caractere din mulţimea {'X', '.'}. Caracterul 'X' corespunde unei celule în care se află o componentă electronică, iar caracterul '.' corespunde unei celule libere.
Celelalte linii din fişier conţin câte 4 numere naturale separate prin spaţii X1 Y1 X2 Y2 cu semnificaţia că trebuie să se verifice dacă componentele electronice situate în celulele de coordonate (X1,Y1) şi (X2,Y2) pot fi sau nu conectate. Celulele (X1,Y1) şi (X2,Y2) sunt distincte. Pe ultima linie din fişier se află 4 valori egale cu 0, indicând sfârşitul datelor din fişier.

Date de ieşire

Fişierul de iesire inginer.out va conţine pentru fiecare pereche de componente din fişierul de intrare o linie pe care va fi scris un număr natural reprezentând rezultatul verificării: 0, dacă componentele din perechea respectivă nu pot fi conectate, respectiv lungimea minimă a unui traseu ce permite conectarea celor două componente.

Restricţii

• 1<=N, M <=75
• Numărul de perechi de componente din fişierul de intrare nu depăşeşte 20

Exemple

inginer.in	inginer.out
4 5 XXXXX X...X XXX.X .XXX. 3 2 3 5 3 1 4 4 3 2 4 3 0 0 0 0	5 6 0

prof. Emanuela Cerchez

Liceul de Informatică „Grigore Moisil” Iaşi

emanuela.cerchez@gmail.com