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 celulă î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.
- Pentru a urca pe spatele lui Percy, Teognis trebuie să se deplaseze către o celulă cu apă în care Percy se afla deja sau în care s-a deplasat în exact acelaşi timp. Analizaţi primul exemplu pentru clarificări în această privinţă.

Comoara magică a ţestoaselor se află undeva pe pământ. Care este timpul minim necesar pentru ca Teognis să ajungă la celula în care se află 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
• Celulele în care se află iniţial Teognis, respectiv comoara, conţin pământ.
• Celula în care se află iniţial Percy conţine apă.
• Se garanteaza ca intotdeauna se poate ajunge la Comoara

Exemplu

Cum se trimit solutii?