Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2011-06-11 06:54:10.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:smart.in, smart.outSursăLot Arad 2011
AutorConstantin GalatanAdăugată deandrei.12Andrei Parvu andrei.12
Timp execuţie pe test0.425 secLimită de memorie128000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Smart

Într-un laborator de cercetări în domeniul geneticii, s-a obţinut o rasă de şoareci inteligenţi. Pentru a demonstra public acest lucru, cercetătorii au introdus k şoareci în celula X a unui labirint format din n x n celule pătratice. Unele celule sunt accesibile, iar altele nu.

Pe fiecare perete care desparte două celule accesibile, se află câte o gaură (de şoarece!) prin care poate să treacă un singur şoarece, iar trecerea durează o secundă. 

Şoarecii participă voluntar la acest experiment şi au înţeles imediat că trebuie să ajungă cu toţii în cel mai scurt timp posibil în celula Y.

Cerinţă

Determinaţi timpul minim necesar pentru ca toţi şoarecii să ajungă în celula Y.

Date de intrare

În fisierul smart.in, se află pe prima linie numerele naturale n şi k, reprezentând dimensiunea labirintului, respectiv numărul de şoareci care au fost de acord să participe la experiment.
Pe fiecare dintre următoarele n linii, se găsesc câte n caractere care codifică labirintul. Caracterul '0' semnifică o celulă accesibilă iniţial neocupată, '1' o celulă inaccesibilă, 'X' este celula accesibilă de plecare, iar 'Y' este celula accesibilă de sosire. 

Date de ieşire

Fisierul smart.out va conţine o singură linie pe care se va scrie un număr T, reprezentând cel mai scurt timp posibil necesar pentru ca toţi şoarecii să ajungă în celula Y.

Restricţii

  • 1 ≤ n ≤ 50
  • 1 ≤ k ≤ 100
  • 2 ≤ numărul de celule accesibile ≤ 300
  • Timpul de deplasare a şoarecilor în interiorul unei celule este neglijabil.
  • Într-o celulă accesibilă se pot afla la un moment dat oricâţi şoareci.

Exemplu

smart.insmart.out
3 4
X00
010
0Y0
5

Explicaţie

Exemplul este cel din figură.

Să notăm cei patru şoareci cu s1, s2, s3 şi s4.
După prima secundă, s1 a trecut în celula B1 şi s2 în celula A2.
După secunda a doua, s1 a ajuns în C1, s2 în A3, iar s3 a intrat în B1.
După secunda a treia, s1 a ajuns în Y, s2 în B3, s3 în C1, iar s4 în B1.
După 4 secunde, s2 ajunge în C3, s3 ajunge în Y, s4 in C1.
După secunda 5, s2 şi s4 au ajuns în celula Y.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?