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 curând la liceu, a început să capete puteri paranormale. Mai exact, el poate controla telepatic ţestoasa mascota a liceului, Percy. Patruns cumva in lumea mistică a ţestoaselor, el doreşte acum să captureze comoara magică a ţestoaselor.

Lumea testoaselor poate fi modelată ca o matrice cu N linii si M coloane, unde fiecare celula contine fie pământ fie apă. Atât lui Teognis cât si lui Percy le ia o unitate de timp sa se deplaseze dintr-o celula într-o altă celulă adiacentă 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
• Pentru 15 de puncte se garanteaza ca N = 1
• Pentru 50 de puncte se garanteaza ca 1 ≤ N, M ≤ 50

Exemplu

Cum se trimit solutii?