| Fişierul intrare/ieşire: | smart.in, smart.out | Sursă | Lot Arad 2011 |
| Autor | Constantin Galatan | Adăugată de |  Andrei Parvu •andrei.12 |
| Timp execuţie pe test | 0.425 sec | Limită de memorie | 128000 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | smart.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.
