== include(page="template/taskheader" task_id="smart") ==
Poveste şi cerinţă...
Î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$.
h2. Cerinţă
Determinaţi timpul minim necesar pentru ca toţi şoarecii să ajungă în celula $Y$.
h2. Date de intrare
Fişierul de intrare $smart.in$ ...
Î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.
h2. Date de ieşire
În fişierul de ieşire $smart.out$ ...
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$.
h2. 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.
h2. Exemplu
table(example). |_. smart.in |_. smart.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3 4
X00
010
0Y0
| 5
|
h3. 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$.
!problema/smart?pic.jpg!
== include(page="template/taskfooter" task_id="smart") ==
