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
