Fişierul intrare/ieşire:	delfin.in, delfin.out	Sursă	Algoritmiada 2018 Runda PreOJI
Autor	Mihai Calancea	Adăugată de	Radu Muntean •heracle
Timp execuţie pe test	0.6 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Delfin

Teognis, de curand la liceu, a inceput sa capete puteri paranormale. Mai exact, el poate controla telepatic testoasa mascota a liceului, Percy. Patruns cumva in lumea mistica a testoaselor, el doreste acum sa captureze comoara magica a testoaselor.
Lumea testoaselor poate fi modelata ca o matrice cu N linii si M coloane, unde fiecare celula contine fie pamant fie apa. Atat lui Teognis, cat si lui Percy le ia o unitate de timp sa se deplaseze dintr-o celula intr-una adiacenta ortogonal; ei au voie sa se deplaseze simultan, dar si sa stea pe loc in timp ce celalalt se misca. Percy se poate afla doar pe apa, iar Teognis doar pe pamant. Comoara magica a testoaselor se aflta pe pamant. Pentru a putea trece peste apa, Teognis trebuie sa se urce pe Percy, care il poate duce peste apa. Care este timpul minim necesar pentru a castiga comoara ?

Date de intrare

Fişierul de intrare delfin.in contine pe prima linie N si M, 2 numere intregi reprezentand dimensiunea matricii ce reprezinta lumea testoaselor
Urmatoarele N linii vor contine cate M caractere, reprezentand matricea ce reprezinta lumea testoaselor. Fiecare celula a matricii contine un caracter, iar intelesul acestora este:

Date de ieşire

În fişierul de ieşire delfin.out se va afla un singur numar, timpul minim de a ajunge la comoara.

Restricţii

• 1 ≤ N, M ≤ 2000

Exemplu

Cum se trimit solutii?