Fișierul intrare/ieșire	inginer.in, inginer.out	Sursă	.campion 2008
Autor	Emanuela Cerchez	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.1 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	3

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Inginer (clasa a 10-a)

Ești inginer la o firmă care construiește circuite integrate și proiectezi un nou circuit integrat pe o plăcuță de x(M+2) milimetri. Pe plăcuță este trasat un caroiaj care împarte plăcuța în 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 electronice. 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 ieșire 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

Exemplu