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 ţestoaselor poate fi modelată ca o matrice cu N linii si M coloane, unde fiecare celulă conţine fie pământ fie apă. Teognis şi Percy se deplasează după următoarele reguli:

- Atât lui Teognis cât si lui Percy le ia o unitate de timp să se deplaseze dintr-o celula într-o altă celulă adiacentă ortogonal (i.e, o celulă vecină pe una din cele patru direcţii cardinale).
- Ei au voie să se deplaseze simultan.
- Percy se va afla permanent pe celule cu apă.
- Teognis poate călători de unul singur doar pe celule cu pământ.
- Teognis poate călători pe apă dacă se află pe spatele lui Percy.

Comoara magică a ţestoaselor se află pe pământ. 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 ≤ 1000
• Pentru 15 de puncte se garantează ca N = 1
• Pentru alte 35 de puncte se garantează ca 1 ≤ N, M ≤ 50

Exemplu

Cum se trimit solutii?