smart

Time limit: 0.25s Memory limit: 128MB Input: smart.in Output: smart.out

Î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 kk şoareci în celula XX a unui labirint format din nnn \cdot 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 YY.

Cerință

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

Date de intrare

În fisierul smart.in, se află pe prima linie numerele naturale nn şi kk, reprezentând dimensiunea labirintului, respectiv numărul de şoareci care au fost de acord să participe la experiment.
Pe fiecare dintre următoarele nn linii, se găsesc câte nn 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 TT, reprezentând cel mai scurt timp posibil necesar pentru ca toţi şoarecii să ajungă în celula YY.

Restricții și precizări

  • 1n501 \leq n \leq 50
  • 1k1001 \leq k \leq 100
  • 22 \leq numărul de celule accesibile 300\leq 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.

Exemplul 1

smart.in

3 4
X00
010
0Y0

smart.out

5

Explicație

Exemplul este cel din figură.

Să notăm cei patru şoareci cu s1s_1, s2s_2, s3s_3 şi s4s_4.
După prima secundă, s1s_1 a trecut în celula B1B_1 şi s2s_2 în celula A2A_2.
După secunda a doua, s1s_1 a ajuns în C1C_1, s2s_2 în A3A_3, iar s3s_3 a intrat în B1B_1.
După secunda a treia, s1s_1 a ajuns în YY, s2s_2 în B3B_3, s3s_3 în C1C_1, iar s4 în B1B_1.
După 44 secunde, s2s_2 ajunge în C3C_3, s3s_3 ajunge în YY, s4s_4 in C1C_1.
După secunda 55, s2s_2 şi s4s_4 au ajuns în celula YY.

Log in or sign up to be able to send submissions!