Fișierul intrare/ieșire	inundatie2.in, inundatie2.out	Sursă	Concurs IQ Academy | Clasele 9-10
Autor	autor necunoscut	Adăugată de	Teodor Plop • teodor94
Timp de execuție pe test	0.25 sec	Limită de memorie	32786 KB
Scorul tău	N/A	Dificultate	N/A

Vezi soluțiile trimise | Statistici

Inundație2 (clasa a 10-a)

Avem o matrice cu N linii și M coloane. În fiecare celulă din matrice se află un număr natural, reprezentând elevația terenului.

Inițial, la momentul de timp t = 0, terenul nu conține apă. Apoi, în fiecare moment de timp t, apa se ridică la o înălțime egală cu t.

Cerință

Vrem să înotăm începând din celula (1, 1), până în celula (N, M), trecând doar prin celule care sunt acoperite de apă. Dintr-o celulă putem înota doar în celulele care au o latură adiacentă (în toate cele 4 direcții). Timpul necesar acțiunii de înot este neglijabil (poate fi considerat nul).

Să se afișeze momentul minim de timp la care acest lucru devine posibil.

Date de intrare

Fișierul de intrare inundatie2.in conține pe prima linie două numere naturale N și M. Pe următoarele N linii se află elementele matricei.

Date de ieșire

În fișierul de ieșire inundatie2.out se găsește un singur număr natural, reprezentând primul moment de timp la care putem traversa matricea din (1, 1) în (N, M), mergând doar pe apă.

Restricții

• 1 ≤ N, M ≤ 500
• 0 ≤ Elevația terenului ≤ 1.000

Exemplu